home *** CD-ROM | disk | FTP | other *** search
/ The Datafile PD-CD 3 / PDCD_3.iso / utilities / utilss / signature / !Signature / NumModTxt < prev    next >
Text File  |  1992-08-01  |  18KB  |  537 lines
  1. NUMBERS MODULE version 0.08
  2. ===========================
  3.  
  4. (C) Copyright Nick Craig-Wood 1992
  5.  
  6. The module "Numbers" and this documentation "NumModTxt" are public domain. 
  7. You may distribute them freely provided that
  8.  1) both files are always kept together
  9.  2) the files are not altered in any way
  10.  3) no profit is made
  11. If you wish to break any of these conditions get in touch with me at the
  12. address below first.
  13.  
  14. The software and documentation was first published in BBC Acorn User
  15. Magazine, September 1992, and for more information see that issue.
  16.  
  17. These routines started life in 1989 written in C on the university mainframe
  18. in response to a  "Numbers Count" puzzle in PCW.  The problem (or part of
  19. it) was to calculate the biggest prime you could find of the form N!+1. 
  20. However the routines did not get finished in time  for the puzzle deadline. 
  21. In the quest for speed I converted the routines to 68000 code for my  Atari
  22. ST, and then a year later into ARM code.  With an ARM3 the routines run at
  23. the same  speed as they did on the mainframe!
  24.  
  25. Numbers are held in application memory area in a heap, and maintained by
  26. OS_Heap.  Before the module can be used, it must be told about this
  27. heap with Num_InitHeap.  Numbers come in two pieces, the head and the tail. 
  28. All numbers have a head, but need not have a tail.  The head of the number
  29. is a short block in the heap, which points to the tail and keeps the length
  30. and sign of the number, and various other things.  Numbers are passed by
  31. reference only, as pointers to the head of the number.  These are refered to
  32. as NUMs.  For example NUM r0 indicates that r0 is a pointer to the head of a
  33. number.
  34.  
  35. Since NUMs are passed by reference only, if you pass them into procedures
  36. and then alter the values of the input parameters, you are actually
  37. altering the NUM.  So to avoid problems, if you write a procedure which
  38. takes NUMs as parameters for both input and output, it is best to define
  39. some temporary NUMs using Num_Init for the output, and then at the end
  40. Num_Swap the results into the correct place, and Num_Remove the temporary
  41. variables.  All the internal routines of the module work like this, so there
  42. is never any problem with passing the same NUM as input and output.
  43.  
  44. Some of the routines take either NUMs or scalars as arguments.  Scalars are
  45. normal signed or unsigned 32 bit numbers.  All routines expect NUMs to be
  46. tidy (except Num_Tidy).  (A num is tidy if its most significant digit is
  47. non-zero, and if it is zero, then it is positive, and of length 1.  Num_Tidy
  48. accomplishes this.  It is unlikely that a user will need this function.)
  49.  
  50. Any error from the numbers module will be prefixed with "Numbers: ".  If you
  51. pass an invalid NUM to any of the routines, the chances are that OS_Heap
  52. will reply with an error, but not one that makes sense always.  The most
  53. confusing is "Numbers: Heap Full" so beware!  See the end for a short example
  54. program.
  55.  
  56. If you find any bugs, have any comments or queries or wish to use the module
  57. in commercial software please write to
  58.  
  59. Nick Craig-Wood
  60. 4 Victoria Street
  61. Wolverton
  62. Bucks
  63. MK12 5HL.
  64.  
  65. -----------------------------------------------------------------------------
  66.  
  67. NUMBERS SWI
  68. ===========
  69.  
  70. On Entry:        r0-r3 are parameters
  71. On Exit:         r0-r3 are returned as results or corrupted
  72.                  r4-r14 are preserved
  73.  
  74. Interrupts:      Interrupts are enabled
  75.                  Fast interrupts are enabled
  76.  
  77. Processor mode:  Processor is in SVC mode
  78.  
  79. Re-entrancy:     SWIs are not re-entrant
  80.  
  81. Use:             See QUICK REFERENCE, and DEFINITIONS for details
  82.                  All SWIs that are capable of looping respond to ESCAPE
  83.                  See ERRORS section for details of errors returned
  84.  
  85. -----------------------------------------------------------------------------
  86.  
  87. QUICK REFERENCE
  88. ===============
  89.  
  90. NUMBERS HEAP: area in application workspace where all the number are kept
  91. HEAD: 16 byte parameter block in the numbers heap pointing to
  92. TAIL: variable length block containing the value of the number
  93. NUM: meaning a 32 bit integer pointing to a HEAD
  94. INT: meaning a 32 bit integer
  95. SCALAR: meaning a 32 bit integer
  96. FLAG: is either 0 for false, or 1 for true
  97. STRING: a pointer to a 0 terminated ASCII string
  98.  
  99. a,b,c,d represent pointers to NUMs
  100. i,j,k   represent SCALARS
  101. p,q     represent a pointer to memory
  102. f       represents a FLAG
  103. h       represents a HeapPointer as returned by Num_HeapInit in r0
  104.           
  105. SWI                 Parameters  Results  Comments
  106. ===                 ==========  =======  ========
  107. Num_Author          -           -        Prints out some info
  108. Num_InitHeap        p,i         h,a,b,c  h<-HeapPointer, a<-0, b<-1, c<-2
  109. Num_MakeSmallPrimes i           j        Makes primes up to i, # found to j
  110.  
  111. (All the SWIs below need a valid NUM or HeapPointer in r0)
  112.  
  113. Num_Allocate        a,i         -        Allocates i words to TAIL of a
  114. Num_Deallocate      a           -        Removes the TAIL of a
  115. Num_Set             a,i         -        Sets a to signed i
  116. Num_USet            a,i         -        Sets a to unsigned i
  117. Num_Init            h           a        Makes a HEAD and TAIL and pointer a
  118. Num_Remove          a           -        Removes the HEAD and TAIL of a
  119. Num_Equals          a,i         f        Returns truth of a = i
  120. Num_Swap            a,b         -        Swaps a and b.  This is quick.
  121. Num_Move            a,b         -        Sets b to a.  Not so quick.
  122. Num_Clear           a           -        Sets TAIL of a to all zeroes
  123. Num_Tidy            a           -        Reduces a to shortest length
  124. Num_UCmp            a,b         i        Unsigned compare of a-b to i
  125. Num_Cmp             a,b         i        Returns the sign of a-b to i
  126. Num_ScalarCmp       a,i         j        Returns the sign of a-i to j
  127. Num_ScalarAdd       a,i,c       -        c <- a + i
  128. Num_ScalarSub       a,i,c       -        c <- a - i
  129. Num_ScalarMul       a,i,c       -        c <- a * i
  130. Num_ScalarDiv       a,i,c       j        c <- a / i, j <- a MOD i
  131. Num_ScalarMod       a,i         j        j <- a MOD i
  132. Num_SmallFactorN    a,i         k        k=smallest factor of a or 0, try i
  133. Num_SmallFactor     a           k        k=smallest factor of a or 0, try all
  134. Num_Add             a,b,c       -        c <- a + b
  135. Num_Sub             a,b,c       -        c <- a - b
  136. Num_Mul             a,b,c       -        c <- a * b
  137. Num_Div             a,b,c,d     -        c <- a / b, d <- a MOD b
  138. Num_Mod             a,b,c       -        c <- a MOD b
  139. Num_Dump            a           -        Prints a in hex, and other info
  140. Num_ToString        a           p,q      Makes STRING of a to p, end=q
  141.                                          After use do SYS "Num_Deallocate",b
  142. Num_Print           a           -        Prints a in decimal
  143. Num_FromString      a,p         f        Converts STRING at p to a, f=ok
  144. Num_Input           a           f        Gets a decimal input to a, f=ok
  145. Num_Info            h           -        Prints memory usage info
  146. Num_RndScalar       h           i        Makes a random number 0-&FFFFFFFF
  147. Num_SetSeed         h,i         -        Sets seed of rnd generator
  148. Num_Rnd             a,b         -        Makes random number to a, 0 <= a < b
  149. Num_Gcd             a,b,c       -        c <- greatest common divisor a,b
  150. Num_Sqr             a,b         -        b <- square root of a
  151. Num_Pow             a,b,c       -        c <- a ^ b (a to the power b)
  152. Num_PowMod          a,d,c,b     -        d <- (a^b) MOD c
  153. Num_Factorial       a,b         -        b <- a! = a*(a-1)*(a-1)*..*3*2*1
  154. Num_Inv             a,b,c,d     -        Finds c,d: a*c MOD b=d & d=GCD(a,b)
  155. Num_FermatTest      a,i         j        Computes truth of i^(a-1) MOD a = 1
  156. Num_ProbablyPrime   a           j        j <- 0 if not prime, 1 probablyprime
  157.  
  158. -----------------------------------------------------------------------------
  159.  
  160. DEFINITIONS
  161. ===========
  162.  
  163. Num_InitHeap
  164. ------------
  165. This expects r0 as a pointer to a block of memory to be used as a heap, and
  166. r1 as the length of this memory in bytes. This returns a pointer to the
  167. heap in r0 and some nums which are useful consants r1 <- zero, r2 <- one, r3
  168. <- two.  The HeapPointer returned in r0 is required by some of the other
  169. routi