*************************************************************************** Subject: Readme file for the RPN large-integer calculator Author : Sjoerd.J.Schaper Date : 12-27-2004 Code : Visual Basic 4.0 ***************************************************************************

Preliminaries Copy "RPNcalc.exe", "bignumVB.dll" and "primflgs.bin" into the same directory. Add "RPNcalc.html" for quick reference. Before you can run this program, you must have installed the 32-bit Visual Basic 4.0 runtime library "vb40032.dll". Download ftp://ftp.microsoft.com/Softlib/MSLFILES/Vb4Run.exe, execute and copy the library into the \Windows\System directory. Usage Note there are no {digit} and {enter} buttons on the form: take the mouse in your left hand, so you can operate the numeric keypad with your right hand. Toggle [Num Lock] On, type numbers with the digit keys, separate multiple numbers with [Enter], and press an operator button to process the bottom of the stack. That's all there is to Reverse Polish (or postfix) Notation (RPN)! Some operations might take forever for big numbers: press F1 or [Alt]+R; B to break-off. Press F4 or [Alt]+R; Q to quit the program. See file "RPNCalc.htm" for a description of all functions. Though {quadr}, {conv}, {exp}, {log}, {p» r} and {r »p} report in decimal format, this calculator does not directly operate on decimal fractions. If input contains a decimal point, first press [Enter] to convert to a rational fraction, then proceed in rational ('Q') mode, or call a rational function. Hexadecimal input has to be indicated with prefix &H: press letter h. Learn more about RPN at http://www.hpmuseum.org/rpn.htm Examples To compute the sum of 2 and 3, key in 2 [Enter] 3 {+} and find the result in the display. {clear} Computing the golden ratio phi to a few hundred decimals is nearly as simple. Key in 1350 {fibo} 1351 {fibo} to push two large consecutive Fibonacci numbers on the stack, then press {conv} to display the decimal expansion of their ratio. Input 55 and press {confrc} {conv} for a much simpler approximation. {clear} Fibonacci fact: F_gcd(m, n) = gcd(F_m, F_n), for example 1717 [Enter] 1919 {gcd} {fibo} equals [Enter] {drop} {drop} {fibo} {x«»y} {fibo} {gcd} {roll} {clear} Pascal's triangle contains the figurate numbers along its diagonals. The triangular numbers T_n = n × (n + 1)/ 2 are found as n + 1 choose 2, for example 2662 [Enter] {inc} {×} {shr} [Enter] equals 2663 [Enter] 2 {bino} {clear} The continued fraction algorithm finds rational approximations to a fraction in decimal notation 1.618034 [Enter] convert to a rational fraction [Enter] {shl} {sqrt} {confrc} gives best approximation F_17 / F_16 {last} {sqrt} {confrc} gives simpler fraction F_9 / F_8. {clear} For the nice continued fraction of cotanh(1) = (e^2 + 1) / (e^2 - 1), key in 2 [Enter] 1 {exp} {sto} {+} [Enter] [Enter] {rcl} {-} [Enter] {confrc} {clear} For the related continued fraction of tan(1) input both absolute value 1 and argument 1 in rational form 1 3 times [Enter] {p» r} and convert to rectangular coordinates cos(1) and sin(1). {drop} {drop} {x«»y} throw away the denominator and reciprocate ratio (x, y) [Enter] {sqrt} {confrc} {clear} Solve 5x^2 + 18x = 15 with the quadratic formula 5 [Enter] 18 [Enter] 15 {quadr} [Enter] {confrc} for the periodic continued fraction. {clear} For calculations with rational numbers, click somewhere on the central frame. It should be coloured blue and have "Q" as caption. The basic operations are customized to work with rationals p/q now. To compute the harmonic mean of 3, 5 and 8, key in 1 [Enter] 3 [Enter] 1 [Enter] 5 {+} 1 [Enter] 8 {+} 1 [Enter] 3 {×} {x«»y} {clear} In musical theory, the small difference between 7 octaves (2:1) and 12 perfect fifths (3:2) is called the Pythagorean comma. To compute its precise harmonic ratio, key in 3 [Enter] 2 [Enter] 12 {a^k} and 2 [Enter] 1 [Enter] 7 {a^k} {÷} you'll find the result in registers Y and X, press {conv} for the full 20-digit decimal expansion. Let's express this microinterval in cents (-the 1200th part of an octave) {log} for a rational approximation of log(interval) 2 [Enter] 1 {log} {÷} divide by log(2) 1200 [Enter] 1 {×} and multiply by 1200. {conv} to view the size in decimal, 50 {confrc} for a small rational approximation. {clear} Compute the first few terms defining Liouville's constant Sum{n=1:inf}10^-n! 1 [Enter] 10 [Enter] 1 [Enter] 100 {+} 1 [Enter] 10 [Enter] 6 {a^k} {+} 1 [Enter] 10 [Enter] 4 {n!} {a^k} {+} 1 [Enter] 10 [Enter] 5 {n!} {a^k} {+} and display its outrageous continued fraction [Enter] {confrc} this is Sloane's sequence A058304. {clear} Stay in rational mode for root-of-unity exp(Pi*2i/3) 1 {chs} [Enter] 0 {r »p} compute a rational approximation of constant Pi 2 [Enter] 3 {×} {p» r} convert the product to rectangular coordinates and find the real and imaginary components of the root. {clear} To compute complex power (3 + 4i)^(4 / 3), input 3 [Enter] 4 {r »p} {sto} convert base to polar coordinates and save argument fi {drop} {drop} {log} 4 [Enter] 3 {×} {exp} compute modulus ^ (4 / 3) {roll} {roll} {rcl} 4 [Enter] 3 {×} {p» r} restore argument fi, multiply by 4 / 3 and convert back to Cartesian coordinates (2.806, 8.076...) Click the frame twice to switch back to normal ('Z') mode. {clear} An indeterminate problem from Master Sun's mathematical manual (the 4th century Sunzi Suanjing): There is an unknown number of things. If we count by threes, there is a remainder 2; if we count by fives, there is a remainder 3; if we count by sevens there is a remainder 2. Now find the number of things. To solve x = 2 mod 3, x = 3 mod 5 and x = 2 mod 7, key in 3 [Enter] 2 [Enter] 5 [Enter] 3 {chinese} 7 [Enter] 2 {chinese} Note that the moduli of each pair are input first. {clear} To find four successive numbers each divisible by a square, key in 11 {a^2} 0 [Enter] 13 {a^2} 1 {chinese} 17 {a^2} 2 {chinese} 19 {a^2} 3 {chinese} To verify, press [Enter] {dcr} [Enter] {dcr} [Enter] {dcr} [Enter] 361 {mod} [Backspc] 289 {mod} [Backspc] 169 {mod} [Backspc] 121 {mod} {clear} An indeterminate problem from E. Bézout's 1766 Cours d'Algèbre: How can you pay a sum of 542 pounds, giving coins of 17 pounds value, and receiving change in 11 pound coins? Key in 17 [Enter] 11 {chs} [Enter] 542 {bezout} Paying 39 * 17 and receiving 11 * 11 makes 542 indeed. {clear} Because the equation my + ax = b is equivalent to the congruence ax = b (mod m), the bezout function is used also for solving a system 17x = -1 (mod 7) and 11x = -2 (mod 15). 7 [Enter] 17 [Enter] 1 {chs} {bezout} solves the first congruence, 15 [Enter] 11 [Enter] 2 {chs} {bezout} solves the second, {drop} {clx} 15 {drop} {drop} {clx} 7 {drop} {drop} {chinese} solves the system. {clear} Iff a number m is prime, then 1 and -1 are the only square roots of 1 modulo m, otherwise there always exists another pair of square roots of unity. Suppose m = 10^8 + 1, 10 [Enter] 8 {a^k} {inc} 1 {modsqr} obtain a non-trivial root of 1 (mod m). The number is associated with itself, so {modinv} verifies the result, as well as {a^2} {x«»y} {mod} The Miller-Rabin pseudoprime test uses the detection of such peculiar roots of 1 to recognize composite numbers. {clear} Find the 7-adic expansion of 2 / 3 to precision O(7^10) 7 [Enter] 10 {a^k} [Enter] [Enter] 3 {modinv} {shl} {x«»y} {mod} compute 2 / 3 (mod 7^10) 1 [Enter] 7 {conv} convert to base 7 and read from right to left. {clear} For both 7-adic branches of square root 2, input 7 [Enter] 10 {a^k} 2 {modsqr} to solve x^2 = 2 (mod 7^10) 1 [Enter] 7 {conv} for the first branch {drop} {-} 1 [Enter] 7 {conv} for the second. {clear} To find the next irreducible rational number after -22/7 with denominator < 113, key in 22 {chs} 7 [Enter] 112 {farey} Find the simplest rational between both fractions {sto} {last} [Enter] {rcl} joins argument and result; click the central frame twice to switch to complex mode, then press {+} to sum the denominators and numerators in a single operation. Press [Enter] {farey} to jump forward and verify. Click the frame to switch back to normal ('Z') mode. {clear} To traverse an aliquot sequence of order four, input 1264460 and repeat {divf} {-} This is equivalent to applying the restricted divisor function. {clear} When 2^89 - 1 was verified by R.E. Powers to be prime, the tenth perfect number was known. Key in 2 [Enter] 88 {a^k} [Enter] {shl} {dcr} {×} {divf}... The sum of the divisors is in register Y now, press {conv} to see that it is equal to twice 2^88 × (2^89 - 1). {clear} A number is called deficient if this ratio is < 2, abundant if it is > 2. The abundance is easily computed, for example 945 {divf} {shl} {-} If gcd(m, 10) = 1, then the length of the decimal period for the reciprocal of m is equal to the order of 10 modulo m. 1 [Enter] 19 {conv} to verify the decimal period has length 18. Press 5 times [Enter], then 10 {modord} to see that 10 belongs to 18 modulo 19. It's easy now to find the least multiple of 19 that consists of nines only {a^k} {roll} {÷} compute the digits in the period of 1/19 {roll} {×} 19 is a full reptend prime, meaning the decimal period for 1/19 has maximal length p - 1. In contrast there are large primes with surprisingly short decimal periods, try ord_333667(10) for example. {clear} Check: If g is a primitive root of m, then g^k is a primitive root of m only if gcd(k, phi(m)) = 1. Suppose m = 242, key in 242 [Enter] 1 {modord} to find phi(m) = 110 and the least primitive root is 7. 2 {gcd} is > 1, so 7^2 shouldn't be primitive modulo m {roll} {roll} {clx} 7 {a^2} {modord} indeed, ord_49(242) < phi(242) but 7^3 is {clx} 7 {×} {modord} {clear} An Euler pseudoprime is a composite number n which satisfies 2^ (n - 1)/ 2 = ± 1 (mod n), for example 561 [Enter] {dcr} {shr} [Enter] 2 {x«»y} {modpwr} According to Wilson's theorem, should 561 be prime, then it must divide 560! + 1 {x«»y} [Enter] {dcr} {n!} {inc} {x«»y} {mod} leaving remainder one. As this infallible method is unfeasible for big numbers, better use {last} {split} {clear} A Fibonacci pseudoprime is a composite number n such that F_(n-e) = 0 (mod n), with e = ± 1 the value of the Kronecker's symbol (5/n), for example 323 [Enter] 5 {modsqr} because (5/323) = -1, divide by F_324 {drop} [Enter] {inc} {fibo} {x«»y} {mod} so n has passed the test. Press {last} {split} to find you're fooled. {clear} To demonstrate the principle of public-key encryption, we'll encode the number of the beast 666 with a 256-bit key. Input 38 {rnd} {prim}... 40 {rnd} {prim}... {sto} two random primes p and q {dcr} {x«»y} {dcr} {×} and compute totient (p - 1)(q - 1). Use public-key exponent k = 101 and solve kx = 1 (mod totient) 101 {modinv} now private-key exponent l is in register X. {drop} {rcl} {×} compute modulus N = p × q, and {roll} {sto} private-key pair (l, N) {clx} 666 [Enter] 101 {modpwr} find ciphertext 666^k (mod N) in register X, to decode with private-key pair (l, N), do {drop} {rcl} {roll} {x«»y} {modpwr} The process is easily repeated with another argument {clx} 10 [Enter] 63 {a^k} 101 {modpwr} and back again {drop} {rcl} {roll} {x«»y} {modpwr} All primes p equal to 1 modulo 4 will factor into conjugate Gaussian primes x ± yi in the ring of complex integers Z[i]. 10 [Enter] 8 {a^k} {inc} {split} 5 times [Enter] {split} factorizes in Z[i]. Press {a^2} {x«»y} {a^2) {+} to verify x^2 + y^2 = p. {clear} This is how you proceed to factorize a Gaussian composite, for example z = 4705 - 8824i 4705 {a^2} 8824 {a^2} {+} computes the norm of z {split} factorizes the norm {split} {drop} {x«»y} {roll} {x«»y} {split} gives both Gaussian prime factors of z. Switch the central frame into complex ('K') mode {chs} {×} and reconstruct the number we started with. Switch back to normal mode. If -1 is square modulo some composite number m, we can find a quadratic representation x^2 + y^2 of m with Cornacchia's continued fractions method. Input 10 [Enter] 40 {a^k} {inc} {split} 5 times [Enter] {dcr} {modsqr}... {roll} [Enter] {sqrt} {confrc} to compute y [Enter] {a^2} {roll} {x«»y} {-} {sqrt} to compute x. This is one of Alf van der Poorten's cute decompositions. {clear} To obtain the same number in a different way, input 0 [Enter] 10 [Enter] 20 {a^k} {inc} enter dividend (10^20 + 1)*i 17 {split} factorize in Z[i] the prime we left out in the above click the central frame twice and press {÷} to compute the complex quotient. Click the frame once more to switch back to normal mode.