BIGNUM.BAS
14 Dec 1996 by Marc Kummel aka Treebeard.
Contact mkummel@rain.org, http://www.rain.org/~mkummel/


  About BIGNUM:
---------------

BIGNUM is a collection of big number arithmetic routines, done with a crypto
project in mind. It's an engaging task to work out these algorithms in BASIC,
since we know them so well on paper.  My aim is to minimize string space; 
then speed.  This is not quite arbitrary precision since numbers, work, and 
the answer must fit in BASIC string space, 64K+ with PDS far strings, much 
less with QBasic.  It's limited by string space and time, not precision.
This can be much optimized, but it works and makes sense.

This program started small, but it grew, maybe too much.  I wrote this with
MS Basic PDS 7.10.  It runs with QB and QBasic, but with much less work
space.  I haven't tried VBDOS or PB.  Check out BNC for a VB3 Windows program
that uses many of the same routines and has even more features, including the
unique ability to turn big numbers into MIDI sound files.  BNC is available
from Treebeard's Basic Vault.

The b_routines can be put in a separate module or library and used in your
own Basic programs if you declare them properly.  Don't use the same string
twice in one call!  bMul s$,s$,s$ should figure s=s*s, but it won't work
because passed strings are modified and restored during the call.  Use 
temporary strings or pass by value, eg bMul (s$),(s$),s$.  See bModPower()
for an example.  Unfortunately, either choice uses more limited string space. 

  
  Using BIGNUM:
---------------

Unzip the archive into a directory, and type BIGNUM to run.  You can place 
BIGNUM.EXE, BIGNUM.PIF, BNLOG.LOG, and BNPRMCNT.DAT in your path.  BIGNUM 
works well in a Win3.1 window.  (A PIF and icon are provided.)

I was mostly interested in the algorithms, so the user interface is simple
by design.  It turns out to be very effective once you learn the keystrokes.
BIGNUM asks for the FIRST number.  Then a SECOND number.  Then an ACTION.
Then it prints the RESULT.  A few keys lead to further options, like <F> to
factor the current result, and then <I> for more number info.  There are lots
of options and shortcuts at each step.  Press <Q> to quit, <?> for help, or 
<Ctrl-Esc> to abort an operation.  Command keys have different meanings as 
inputs or actions.  Upper/lower case doesn't matter.

Here are the details:

  Commands that always work:
  --------------------------
    h or ?            help (this screen)
    i                 info on memory use
    q                 quit the program
    <Enter>           repeat last input or action
    <Ctrl-Esc>        emergency exit if it hangs, but try <Esc> first
  
  Input Commands:
  ---------------
    <Esc>             clear input line
    +6 or +-6         add (etc) 6 or -6 to last input
    -                 change the sign of last input
    6.06...           6.060606... to digits places
    66a               66 degree angle in radians
    6ab16             enter value 6A in base 16, bases to 32K are ok
    66,6b100          enter 66*100+6 in base 100
    a or -a           last answer or its negative
    d or w            decimal or whole part of last answer
    e10               e to 10 (or digits) places
    6.6e6             6.6 x 10^6 in scientific notation
    k66               66th prime (2 is the first)
    m[0-9]            get value from memory cell 0-9
    66m[0-9]          enter value and store it in memory cell 0-9 (m=0)
    o10               pi to 10 (or digits) places ("o" for circle)
    p66               smallest prime >= 66
    r6.6              random with 6 digits before decimal and 6 after
    r66.              random with 66 digits and random decimal point
    s66,6             string of 66 6s for big test numbers
    x                 exchange last input (a=last b or b=last a)
    z                 pop value from stack (or 0)
  
  Action Commands (a is FIRST, b is SECOND):
  ------------------------------------------
    <Esc>             abort calculation (maybe), also try <Ctrl-Esc>
    + - * /           as expected
    \ %               integer and remainder of division
    ^ % !             a^b, a mod b, and a!
    *66               a*b (mod 66), also + - \ but not ^
    /66               divide (etc) and figure 66 digits for this calc only
    =                 compare, return 1 if a>b, 0 if a=b, -1 if a<b
    1 2               pass a or b to result
    a                 a degree angle to radians, or reverse if b=-1
    b                 a base b
    c                 cos(a), or arccos(a) if b=-1 (radians)
    d66               set 66 digits for division (etc) (default=30)
    e                 exp(a) or e^a, e=2.71828...
    f                 smallest prime factor of a, or a if prime
    g                 GCD(a,b), greatest common divisor
    j66               justify (round) a to 66th decimal, or truncate if 0
    k                 binomial coefficient aCb
    l                 LCM(a,b), least common multiple
    m66               a^b (mod 66), or inverse mod 66 if b=-1
    n                 log(a) base b, or ln(a) if b=0 (return n, b^n=a)
    o66               pi to 66 places ('o' for circle)
    p                 aPb, permutations of a items b at a time
    r                 b root of a
    s                 sin(a), or arcsin(a) if b=-1 (radians)
    t                 tan(a), or arctan(a) if b=-1 (radians)
    u                 <nada>
    v                 1/a inverse
    w                 integer square root of a
    x                 do nothing
  
  Result Commands:  
  ----------------
    + - * /           add (etc) memory cell 0 with result and store
    b                 change number base
    f                 factor result
    m or 0-9          put result in memory cell 0-9 (m=0)
    p                 print to LPT1:
    r                 ratio of result
    s                 save to Log file
    z                 push result to stack
    <space>           number theory info or continue
    p                 primality test working factor after abort
    s                 save to Log file
    b d s p t         take biggest factor (etc) as answer
 
There's lot of commands, but this HELP is always available by pressing <H> 
or <?>.


  File list:
------------
  
  BIGNUM.EXE    DOS executable for x286 or better
  BIGNUM.ICO    an icon for Win3.1
  BIGNUM.PIF    Win3.1 pif file, works well in a window
  BNLOG.LOG     log file for saved calculations
  BNPRMCNT.DAT  prime number table, not needed but speeds up factoring
  README.TXT    this file
  TBVAULT.TXT   about Treebeard's Basic Vault
  ------------
  BIGNUMxx.BAS  Basic source code
  PRMCNT.BAS    Basic program to build BNPRMCNT table
  MAKE.BAT      batch file to compile and link from DOS prompt
  XQB.BAT       batch file to start PDS and load code


  Guidance from:
----------------
  
  H. Davenport, The Higher Arithmetic, Dover, 1983 (reprint of 1952)
  Martin Gardner, Tests of Divisibility, The Unexpected Hanging, p.160
  Robert T. Kurosaka, Euclid's Algorithm, Byte, Jan 1986, p.397
  Paul A. Nilson, Algorithms for a Variable-Precision Calculator, Byte,
    Jan 1985, p.211
  Paulo Ribenboim, The Little Book of Prime Numbers, Springer-Verlag, 1991
  Peter Rice, Arithmetic on your PC, Byte, Mar 1985, p.119
  Neville Robbins, Beginning Number Theory, Wm.C.Brown Publishers
  Dan Sandberg, An Algorithm That Converts Decimals To Fractions, Byte,
    May, 1985, p.429
  Bruce Schneier, Applied Cryptography, John Wiley & Sons, 1996, chap.11
  Samuel Selby, CRC Standard Mathematical Tables, CRC Press, Inc.
  John Smith, Public Key Cryptography, Byte, Jan 1983, p.198
  John David Stone, Fundamentals of Computer Science II: Bignums,
    http://www.math.grin.edu/~stone/courses/fundamentals/bignums.html
  David Wells, The Penguin Dictionary of Curious and Interesting Numbers,
    Penguin Books, 1986
  Various posts in sci.math, sci.math.num-analysis, and sci.crypt


  Conditions:
-------------

This program and source code are yours to use and modify as you will, but 
they are offered as freeware with no warranty whatsoever.  Give me credit, 
but do not distribute any changes under my name, or attribute such changes 
to me in any way.  You're on your own!  

Send comments and fixes to:

  Marc Kummel aka Treebeard
  mkummel@rain.org
  http://www.rain.org/~mkummel/

For more interesting Basic software with source code, check out Treebeard's 
Basic Vault at http://www.rain.org/~mkummel/basic/