COMP 2012H0 Assignment 40Integer Factorization Solution

In this programming assignment, you will have a taste of speed programming.0You are going to solve a classic problem - integer factorization -0which is a key in important applications such as RSA public-key encryption in0a speedy manner.

Please read the FAQ section regularly, and do check it0one day before the deadline to make sure you don't miss any clarification,0even if you have already submitted your work by then. You can also raise questions0on Piazza and remember to use the "pa4" tag.

End of Introduction

Description

Basically, we want to perform factorization for all integers in a given range and print the0results.

The input arguments will be from the command line. You may read this article0to learn about how you might retrieve them in C++. To provide command line arguments to your0program you will have to compile and run your program in a terminal. Please feel free to do0that in any

https://course.cse.ust.hk/comp2012h/assignments/PA4/Description/ 1/7

9:49 PM COMP 2012H Assignment 4: Integer Factorization

terminal you are familiar with.0However, if you want to time your program, you may want to use our0lab 2 Linux machines. Instructions can be found in the next section: Timing your program.

Assuming the name of your program is factorize, we may use the following0command in the terminal:

factorize [range_start] [range_end]

The [range_start] and [range_end] are the integers that0specify the range. For0example, factorize 12 23 will print out the factorization results for all0integers in the range [12, 23] in ascending order like so:

12=2*2*30

13=130

14=2*70

15=3*50

16=2*2*2*20

17=170

18=2*3*30

19=190

20=2*2*50

21=3*70

22=2*110

23=230

The output is pretty straightforward as you can see: each line consists of0the integer being factorized at the beginning, then the equal sign, and finally the factorization result with0a single endl character added at the end. The prime factors, which are0separated by asterisks, in the factorization result must also be listed in ascending order.

Your program should output nothing else and require no user interaction.0(i.e. don't need to take in any standard console input with cin)

For simplicity, you can assume the provided input arguments0[range_start] and0[range_end]

are positive integers between 2 and 263 - 1 inclusively (i.e.0it can be0stored in a

variable), and that [range_start] is no larger0than [range_end].

End of Description

Timing your program

We will be using the time Linux utility to measure the runtime performance of0your0program. You may use this utility on any of our CS Lab 2 (Linux Lab) machines either locally0in0the lab or remotely via SSH. The following shows you how using the SSH client in the Virtual0Barn. You may adjust the steps accordingly if you are familiar with installing and using0a0SSH client on your own computer.

1. Remote control a Windows machine in HKUST0virtual barn. After following the installation guide and user guide there to0install the remote control client and connect to the HKUST network, choose the0Programming Software server when you are offered a selection of different servers.

2. Copy your files to Virtual Barn. If you have no idea how, you can email yourself the0files and then download them there.

3. Open PuTTY. There is a shortcut on your Desktop.0Enter csl2wk13.cse.ust.hk as the Host Name. Note: If0that one server doesn't work, you may try other servers such as

https://course.cse.ust.hk/comp2012h/assignments/PA4/Description/ 2/7

9:49 PM COMP 2012H Assignment 4: Integer Factorization

csl2wk14.cse.ust.hk and csl2wk15.cse.ust.hk. The server number0goes up to at0least 40.0

4. Click Open. If a warning about the security key shows up, click Yes to dismiss it.0

5. Enter your CSD login and password. (Register one if you haven't done so in lab 1 by following0the lab 1 instructions.) It may not show what you type when you are typing in the0password. Don't worry, just type your password and hit the Enter key. You should login0to your home directory. Enter the command pwd (Print Working0Directory) to verify this. It0should show /homes/your_login0

6. Open FileZilla from Start Menu. Click "File" ->0"Site Manager" -> "New Site". Choose SFTP for protocol according to the0screenshot below. Enter csl2wk13.cse.ust.hk (or whatever server you used in a previous step) as Host. Choose "Ask for password" for the

https://course.cse.ust.hk/comp2012h/assignments/PA4/Description/ 3/7

9:49 PM COMP 2012H Assignment 4: Integer Factorization

Logon Type.0

7. Click Connect and then enter your CSD login and password.

8. If the connection succeeds, the right side should show your home directory at Linux Lab. Copy your factorize.cpp file by dragging it to the right side. That would upload the0file to

/homes/your_login. You can close FileZilla after doing0so.

9. Go back to PuTTY, and compile your program using the0following command:

g++ -Wall -Wextra -pedantic -std=c++11 -o factorize factorize.cpp

10. If no compilation errors occur, you should be able to time and run your program by adding /usr/bin/time -v before the command to be timed. For example:

/usr/bin/time -v factorize 9234567890 9234567899

Output like the following will be printed:

https://course.cse.ust.hk/comp2012h/assignments/PA4/Description/ 4/7

9:49 PM COMP 2012H Assignment 4: Integer Factorization

csl2wk13:yourusername:69> /usr/bin/time -v factorize 9234567890

92345678990

9234567890=2*5*53*73*2386810

9234567891=3*3*3*3*3*19*127*157490

9234567892=2*2*11*17*37*3336670

9234567893=191*317*1525190

9234567894=2*3*907*937*18110

9234567895=5*7*2638447970

9234567896=2*2*2*23*47*229*46630

9234567897=3*31*103*353*2731

9234567898=2*46172839490

9234567899=43*61*35206130

• 0 Command being timed: "factorize 9234567890 9234567899"0

• 0User time (seconds): 10.64

• 0System time (seconds): 0.000

• 0Percent of CPU this job got: 99%0

• 0Elapsed (wall clock) time (h:mm:ss or m:ss): 0:10.650

• 0Average shared text size (kbytes): 00

• 0Average unshared data size (kbytes): 00

• 0Average stack size (kbytes): 00

• 0Average total size (kbytes): 00

• 0Maximum resident set size (kbytes): 3244

• 0Average resident set size (kbytes): 00

• 0Major (requiring I/O) page faults: 00

• 0Minor (reclaiming a frame) page faults: 1230

• 0Voluntary context switches: 20

• 0Involuntary context switches: 50

• 0Swaps: 00

• 0File system inputs: 00

• 0File system outputs: 00

• 0Socket messages sent: 00

• 0Socket messages received: 00

• 0Signals delivered: 00

• 0Page size (bytes): 40960

• 0Exit status: 00

0 0 0 0 0 0

For timing purpose, we will be using the "User time0(seconds)". In0this example, it0took our unoptimized program 10.64 seconds to factorize ten integers between09234567890 and 9234567899.

End of Timing your program

Sample program

On a lab 2 Linux machine (you can access it according to the instructions in Timing your program), you can download our unoptimized sample program0with this command:

wget

https://course.cse.ust.hk/comp2012h/assignments/PA4/Resources/factorize

Note: the downloaded file may be renamed to something else if you already have a file named "factorize" in the current directory - see the output of the wget command to find out what0the sample program has been renamed to.

Then you can add the executable permission to it:

chmod u+x factorize

https://course.cse.ust.hk/comp2012h/assignments/PA4/Description/ 5/7

9:49 PM COMP 2012H Assignment 4: Integer Factorization

Finally you may run it as usual:

factorize 12 20

Windows demo program is provided, but please keep in mind that we grade your codes in Linux lab, so0it is recommended that you check your codes in Linux at least once before the deadline.

Sample program

Sample output

Your finished program should produce the same output as our sample0output. The file names indicate the input arguments used. Please note that sample0output, naturally, does not show all possible cases. It is part of the assessment for you to0design your own test cases to test your program. You may use our sample0program to generate more test cases for yourself. Be reminded to remove any0debugging message that you might have added before submitting your final submission.

Sample output

Submit a single source file factorize.cpp to ZINC.

Cite External Materials

If you have referred to any external materials, please cite them in your ZINC submission. Add a comment at the beginning (line 1) of the source file. If you have already submitted, please kindly add the references (if any) and submit again. It is fine to learn ideas and algorithms from external materials, but you have to write the codes yourself.

Grading scheme

Your program should generate the exact same output as our sample program's.

Your program should run no significantly slower than our unoptimized sample program. That means its running time cannot be more than double of that of ours. For example, if our sample program can generate the results in 5 seconds, your program should not take more than 10 seconds to do the same.

You need to fulfill both requirements to be considered as correct for a test case. We will0test your program on multiple hard test cases (very large number) for multiple times and the0result (average time for one test case) will be released. This will happen outside ZINC as0it doesn't support timing. In ZINC, we only provide a simple test case that factorizes 2 to0100 to help you debug.

Speed programming competition (Bonus)

For this assignment, we will also reward the students that have mastered the art of speed programming up to 10 bonus points.

Your last submission on ZINC will be used for the ranking. No separate submission will be accepted.

Late submission will be excluded from ranking.

We only rank those programs with correct outputs. If your program does wrong in any test0cases, it will be excluded from ranking.

Programs running not that fast will be excluded from ranking. If your running time >01.1 × running time of the demo program, it will not be ranked.

https://course.cse.ust.hk/comp2012h/assignments/PA4/Description/ 6/7

9:49 PM COMP 2012H Assignment 4: Integer Factorization

Hardwares for grading

Currently, the plan is to grade the submissions on CS Linux Lab machines, so:

Please make sure your program can be compiled with this0command on the above mentioned0machines0

g++ -Wall -Wextra -pedantic -std=c++11 -O3 factorize.cpp -o factorize

The above mentioned machines each has 8GB memories in total, and definitely we can never0occupy all of them, so make sure your program's memory use is reasonable. Maybe you can0test it yourself before the final submission. Your program will not be able to access the network.

End of Submission & Grading

Frequently Asked Questions

Q: My code doesn't work, here it is, can you help me fix it?

A: As the assignment is a major course assessment, to be fair, you are supposed to0work on it by yourself and we should never finish the tasks for you. We are happy to help with explanations and0advice, but we are not allowed to directly debug for you.

Q: Can I refer to external materials?0

A: It is fine to learn ideas and algorithms from external materials, but you have to write the codes yourself. Also, please cite the materials you referred to in your submission. Add a comment at the beginning (line 1) of the source file.

End of FAQ

Maintained by COMP 2012H Teaching Team © 2022 HKUST Computer Science0and Engineering

https://course.cse.ust.hk/comp2012h/assignments/PA4/Description/ 7/7