In section 4.5.4 of Knuth's TAOCP, he gives this version of Pollard's famous "rho" algorithm in Algorithm B (page 385 of the 3rd edition); the variable "N" indicates the number to be factored (the input argument, if you like.) (Note that "%" below represents the modulo operator).
Your assignment is to write programs implementing this function in C, Racket, and Gauche.
Your programs should be able to factor the following numbers on cop3353.org:
The programming languages that you are to use for the assignment are:
Your code must compile and run on the cop3353.org server (see last note for details about logging in.)
Note that Gauche and Racket are both dialects of Scheme; once you write your code in one, you can largely re-use the same code for the other.
Your output should look like the following (order of factors reported is not important, though this algorithm tends to be better at finding smaller factors):
COP4020_test@cop3353:~% ./kr 35 Attempting to factor N = 35 with Pollard rho algorithm from Knuth's Algorithm B in section 4.5.4 of TAOCP Factors are: 7 5 COP4020_test@cop3353:~% ./kr.gosh 35 Attempting to factor N = 35 with Pollard rho algorithm from Knuth's Algorithm B in section 4.5.4 of TAOCP Factors are: 7 5 COP4020_test@cop3353:~% ./kr.racket 35 Attempting to factor N = 35 with Pollard rho algorithm from Knuth's Algorithm B in section 4.5.4 of TAOCP Factors are: 7 5 COP4020_test@cop3353:~% ./kr 367756293167964701 Attempting to factor N = 367756293167964701 with Pollard rho algorithm from Knuth's Algorithm B in section 4.5.4 of TAOCP Factors are: 7 11 13 107 101 103 109 3001 1009 COP4020_test@cop3353:~% ./kr.gosh 367756293167964701 Attempting to factor N = 367756293167964701 with Pollard rho algorithm from Knuth's Algorithm B in section 4.5.4 of TAOCP Factors are: 7 11 13 107 101 103 109 3001 1009 COP4020_test@cop3353:~% ./kr.racket 367756293167964701 Attempting to factor N = 367756293167964701 with Pollard rho algorithm from Knuth's Algorithm B in section 4.5.4 of TAOCP Factors are: 7 11 13 107 101 103 109 3001 1009 COP4020_test@cop3353:~% ./kr 2688307493077732358348134727 Attempting to factor N = 2688307493077732358348134727 with Pollard rho algorithm from Knuth's Algorithm B in section 4.5.4 of TAOCP Factors are: 689816117 7688151521 506901611 COP4020_test@cop3353:~% ./kr.gosh 2688307493077732358348134727 Attempting to factor N = 2688307493077732358348134727 with Pollard rho algorithm from Knuth's Algorithm B in section 4.5.4 of TAOCP Factors are: 689816117 7688151521 506901611 COP4020_test@cop3353:~% ./kr.racket 2688307493077732358348134727 Attempting to factor N = 2688307493077732358348134727 with Pollard rho algorithm from Knuth's Algorithm B in section 4.5.4 of TAOCP Factors are: 689816117 7688151521 506901611 COP4020_test@cop3353:~% ./kr 12902144921579660477018619711827 Attempting to factor N = 12902144921579660477018619711827 with Pollard rho algorithm from Knuth's Algorithm B in section 4.5.4 of TAOCP Factors are: 359195201 35919591591591616161427 COP4020_test@cop3353:~% ./kr.gosh 12902144921579660477018619711827 Attempting to factor N = 12902144921579660477018619711827 with Pollard rho algorithm from Knuth's Algorithm B in section 4.5.4 of TAOCP Factors are: 359195201 35919591591591616161427 COP4020_test@cop3353:~% ./kr.racket 12902144921579660477018619711827 Attempting to factor N = 12902144921579660477018619711827 with Pollard rho algorithm from Knuth's Algorithm B in section 4.5.4 of TAOCP Factors are: 359195201 35919591591591616161427
There are separate submission links for each of these assignments. Please just turn in one file for each; for the C program, turn in your source file called "kr.c" and which should require the GMP library. For the Gauche version, turn in your source file called "kr.gosh". For the Racket version, turn in your source file called "kr.racket".
There are two possible due dates for this assignment. The first is the "extra credit deadline", which is 11:59pm on November 6th. For each successful program that you turn in by November 6th, you will receive 1 point of extra credit for the class.
The second deadline is the "regular credit deadline", which is 11:59pm on November 13th. The advantage to using this deadline is that on November 7th, I will discuss in some detail how to write all three of the versions.
Please note that I am allowing only one submission for each of these versions.
Since the Racket and Gauche interpreters on the linprog servers don't seem to have survived the migration from Gentoo to CentOS, you can find these on cop3353.org. To login into cop3353.org, you will need to use the private key matching the public key that you submitted for assignment one.