***************************************************************************
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:
all data entry is done with the numeric keypad.
Toggle [Num Lock] On, enter 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.html" for a description of all functions.
Though {a/b} {1/a} and {funit} write data in decimal format,
this calculator does not operate on decimal fractions!
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 {a/b} to display the decimal expansion of their ratio.
Input 50 and press {confrc} {a/b} for a much simpler approximation.
{clear}
Fibonacci fact: F_gcd(m, n) = gcd(F_m, F_n), for example
1717 [Enter]
1919 {sto}
{gcd} {fibo}
[Enter] [Enter] equals
{rcl} {fibo} {x«»y} {fibo}
{gcd} {-}
{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}
Use the continued fraction algorithm to find rational
approximations of a fraction f in decimal notation.
First count the number of digits n to the right of the
decimal point. Next input f without the decimal point,
input n and press {10^k}. Fraction f is now expressed
as a rational with power-of-ten denominator.
Press [Enter] {shr} {sqrt} {confrc} to compute the best
approximation, or try a smaller last argument to simplify.
Suppose f = 1.618034, so n = 6
1618034 [Enter]
6 {10^k}
[Enter] {shr} {sqrt} {confrc}
gives F_17 / F_16
{last} {shr} {sqrt} {confrc}
gives F_9 / F_8.
{clear}
For calculations on 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 music 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} [Enter]
and
2 [Enter]
1 [Enter]
7 {a^k} {÷}
you'll find the result in registers Y and X,
press {a/b} for the full 20-digit decimal expansion.
Click the frame twice to switch back to normal 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
2 [Enter]
3 [Enter] [Enter]
5 {chinese}
2 [Enter]
7 {chinese}
you'll find modulus 105 in the display,
exchange {x«»y} to show solution 23.
Press 4 times [Enter] to push 23 to the top of the stack, so it
will be copied down after each ensuing operation, then key in
3 {mod}
{clx} 5 {mod}
{clx} 7 {mod}
This verifies the result.
{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 [Enter]
542 {bezout}
This is how you proceed to verify:
first press {sto} {last} [Enter] [Enter] {rcl}
to join arguments and results
{x«»y} {roll} {×}
compute a * x
{drop} {x«»y} {drop} {×}
compute b * y
{x«»y} {drop} {-}
Because the equation ax - my = 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 4 times [Enter]
17 {x«»y} [Enter]
1 {chs} {bezout}
solves the first congruence,
{drop} {x«»y} {sto} {clx}
15 4 times [Enter]
11 {x«»y} [Enter]
2 {chs} {bezout}
solves the second,
{drop} {x«»y} [Enter] [Enter]
{rcl} {chinese}
solves the system.
{+} 4 times [Enter]
17 {×} [Enter]
7 {mod}
{clx} 11 {×} [Enter]
15 {mod} verifies the result.
Function {modsqr} gives some solution of x^2 = a (mod m).
Suppose a = -1 and m = 10^8 + 1
8 {10^k} 4 times [Enter]
{inc} {modsqr}
gives one root,
{x«»y} {-} its complement.
Now find another solution, press
{drop} {inc} {split}
to obtain two factors of m (all factors, in fact}
{roll} {x«»y} {modsqr}
{roll} [Enter] {roll} {modsqr}
first solve both quadratic congruences
{roll} {chs} {roll} {chinese}
combine the solutions into a second root,
{x«»y} {-} also compute its complement.
{clear}
To find four successive numbers
each divisible by a square, key in
11 {a^2} [Enter]
1 {chs}
13 {a^2} {chinese}
2 {chs}
17 {a^2} {chinese}
3 {chs}
19 {a^2} {chinese}
{x«»y} 4 times [Enter]
{clx} 121 {mod}
{drop} {inc} {roll}
{clx} 169 {mod}
{drop} {inc} {inc} {roll}
{clx} 289 {mod}
{drop} {inc} {inc} {inc} {roll}
{clx} 361 {mod}
{clear}
To find the next irreducible rational number after -22/7
with denominator < 113, key in
22 {chs}
7 [Enter]
112 {farey}
To find the simplest rational between both fractions, press
{sto} {last} [Enter] {rcl}
to join argument and result
{drop} {x«»y} {roll} {+}
sum the denominators
{drop} {+} {roll}
sum the numerators.
Press [Enter]
{dcr} {farey} to jump forward and verify.
{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
{a/b}
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.
19 4 times [Enter]
{1/a}
to verify the period has length 18
10 {x«»y} {modord}
and see that 10 belongs to 18 modulo 19.
It's now easy to find the least multiple of
19 that consists only of nines
{drop} {10^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.
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. Key in
242 4 times [Enter]
1 {x«»y} {modord}
to find phi(m) = 110 and the least primitive root of m is 7.
{sto} {clx}
2 {gcd}
so 7^2 shouldn't be primitive modulo 242
{clx} 7 {a^2}
{roll} {modord}
but 7^3 is
{rcl} {clx}
3 {gcd}
{clx} 7 {×}
{roll} {modord}
If a number m has a primitive root, then 1 and -1 are
the only square roots of 1 modulo m, otherwise there
always exists another pair of square roots of 1.
1 4 times [Enter]
8 {10^k} {inc} {split}
factorizes m
{roll} {chs} {x«»y} {chinese}
combines into a non-trivial root of 1. Press
{modinv} to verify the result,
{x«»y} {-} to compute the root's complement.
The Miller-Rabin pseudoprime test uses the detection of
such peculiar roots of 1 to recognize composite numbers.
{clear}
An Euler pseudoprime is a composite number n which
satisfies 2^ (n - 1)/ 2 = ± 1 (mod n), for example
2 [Enter]
561 [Enter]
{dcr} {shr}
{x«»y} {modpwr}
According to Wilson's theorem, should 561 be prime,
then it must divide 560! + 1
[Enter] {dcr} {n!} {inc}
{x«»y} {mod}
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
5 [Enter]
323 {modsqr}
because (5/323) = -1, divide by F_324
[Enter] {inc} {fibo}
{x«»y} {mod}
so n has passed the test. Press
{last} {split} to find you're fooled.
To demonstrate the principle of public-key encryption, we'll
encode the number of the beast 666 with a 256-bit key. Input
101 4 times [Enter]
the stack is now loaded with public-key exponent k.
35 {rnd} {prim}...
43 {rnd} {prim}...
{sto} two random primes p and q
{dcr} {x«»y} {dcr} {×}
compute totient (p - 1)(q - 1)
{modinv}
solve 101x = 1 (mod totient) to find private-key exponent l = x
[Enter] {rcl} {×}
compute modulus N = p × q, and
{sto} private-key l, N
{bits} to see its bitlength and population count.
{x«»y} {clx}
666
{x«»y} {drop} {x«»y} {roll}
{modpwr}
find ciphertext 666^k (mod N) in register Y,
then press [Enter]
{rcl} {modpwr}...
to decode with private-key l, N.
{drop} {clx}
63 {10^k} {x«»y} {roll}
{modpwr}
[Enter] {rcl} {modpwr}...
Repeats the process with another argument.
{clear}
To compute the continued fraction expansion of square root 19
and a 324-digit best rational approximation, key in
19 [Enter]
1292 [Enter]
{shr} {drop}
{10^k} {×} {sqrt}
{roll} {10^k}
[Enter] {shr} {sqrt} {confrc}
{sto}
{a/b} for the decimal expansion.
All primes p equal to 1 modulo 4 will factor into conjugate
Gaussian primes x ± yi in the ring of complex integers Z[i].
8 {10^k} {inc}
{split} 4 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 [Enter]
8824 {a^2} {x«»y} {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
40 {10^k} {inc}
{split} 4 times [Enter]
{dcr} {x«»y} {modsqr}...
[Enter] {shr} {sqrt} {confrc}
to compute y
[Enter] {a^2}
{roll} {x«»y} {-} {sqrt}
to compute x.
{x«»y}
This is one of Alf van der Poorten's cute decompositions.
{clear}
To obtain the same number in a different way, input
20 {10^k} {inc}
enter dividend 10^20 + 1
{roll} 17 {split}
factorize in Z[i] the prime we left out in the above.
Click the central frame twice and press
{chs} {÷}
to compute the conjugate complex quotient.
Click the frame once more to switch back to normal mode.
Copyright © december 2004 by Sjoerd.J.Schaper