home *** CD-ROM | disk | FTP | other *** search
/ Frozen Fish 1: Amiga / FrozenFish-Apr94.iso / bbs / oct93 / develop / umbscheme.lha / UMBScheme / src / bignum.c < prev    next >
C/C++ Source or Header  |  1992-08-04  |  22KB  |  1,125 lines
  1. /* bignum.c -- UMB Scheme, implementation of bignum numbers. 
  2.  
  3. UMB Scheme Interpreter                  $Revision: 2.5 $
  4. Copyright (C) 1988, 1991 William R Campbell
  5.  
  6. This program is free software; you can redistribute it and/or modify
  7. it under the terms of the GNU General Public License as published by
  8. the Free Software Foundation; either version 1, or (at your option)
  9. any later version.
  10.  
  11. This program is distributed in the hope that it will be useful,
  12. but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14. GNU General Public License for more details.
  15.  
  16. You should have received a copy of the GNU General Public License
  17. along with this program; if not, write to the Free Software
  18. Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  19.  
  20. UMB Scheme was written by Bill Campbell with help from Karl Berry,
  21. Barbara Dixey, Ira Gerstein, Mary Glaser, Kathy Hargreaves, Bill McCabe,
  22. Long Nguyen, Susan Quina, Jeyashree Sivasubram, Bela Sohoni and Thang Quoc Tran.
  23.  
  24. For additional information about UMB Scheme, contact the author:
  25.  
  26.     Bill Campbell
  27.     Department of Mathematics and Computer Science
  28.     University of Massachusetts at Boston
  29.     Harbor Campus
  30.     Boston, MA 02125
  31.  
  32.     Telephone: 617-287-6449        Internet: bill@cs.umb.edu
  33.  
  34. */
  35.  
  36. #include "portable.h"
  37. #include "eval.h"
  38. #include "object.h"
  39. #include "architecture.h"
  40. #include "number.h"
  41. #include "fixnum.h"
  42. #include "bignum.h"
  43. #include "rational.h"
  44. #include "real.h"
  45. #include "complex.h"
  46. #include "steering.h"
  47. #include "io.h"
  48. #include <math.h>
  49. #include <errno.h>
  50.  
  51. #define Most_Significant_Digit(num) \
  52.             (Get_Number_Digit( (num) , Get_Number_Length(num) - 1 ))
  53.  
  54.  
  55. Private Short    Bignum_Compare();
  56. Private    void    Delete_Leading_Zeros();
  57. Public    void    Long_Division();
  58.  
  59.  
  60. /* REPRESENTATION */
  61.  
  62. #define MAX_DIGIT        (RADIX-1)
  63.  
  64. #define Low_16(long)        (((long) >= 0) ? (Short) ((long) % RADIX) \
  65.                           : (-(Short) (-(long) % RADIX)))
  66.  
  67. #define High_16(long)    (((long) >= 0) ? (Short) ((long) / RADIX) \
  68.                           : (-(Short) (-(long) / RADIX)))
  69.  
  70. #define Integer_Digit(n,i)    ((Integer) Get_Number_Digit(n,i))
  71.  
  72.  
  73. #define max(a,b) ((a) > (b) ? (a) : (b))
  74. #define min(a,b) ((a) < (b) ? (a) : (b))
  75.  
  76.  
  77. /* Predicates. */
  78.  
  79. Public Boolean Is_Bignum_Zero()
  80. {
  81.     return (Number_Sign(Top(1)) == 0);
  82. }
  83.  
  84.  
  85. Public Boolean Is_Bignum_Positive()
  86. {
  87.     return (Number_Sign(Top(1)) > 0);
  88. }
  89.  
  90.  
  91.  
  92. Public Boolean Is_Bignum_Negative()
  93. {
  94.     return (Number_Sign(Top(1)) < 0);
  95. }
  96.  
  97.  
  98.  
  99. Public Boolean Is_Bignum_Odd()
  100. {
  101.     return (! Is_Bignum_Even());
  102. }
  103.  
  104.  
  105.  
  106. Public Boolean Is_Bignum_Even()
  107. {
  108.     return ( (Get_Number_Digits(Top(1))[0] % 2) == 0);
  109. }
  110.  
  111.  
  112.  
  113. Public Boolean Is_Bignum_Exact()
  114. {
  115.     return( TRUE ); 
  116. }
  117.  
  118.  
  119.  
  120. Public Boolean Is_Bignum_Inexact()
  121. {
  122.     return( FALSE );
  123. }
  124.  
  125.  
  126.  
  127.  
  128. /* General comparison. */
  129.  
  130. Public Boolean Bignum_Equal()
  131. {
  132.     return Bignum_Compare() == 0;
  133. }
  134.  
  135.  
  136.  
  137. Public Boolean Bignum_Less_Than()
  138. {
  139.     return Bignum_Compare() < 0;
  140. }
  141.  
  142.  
  143.  
  144. Public Boolean Bignum_Greater_Than()
  145. {
  146.     return Bignum_Compare() > 0;
  147. }
  148.  
  149.  
  150.  
  151. Public Boolean Bignum_Less_Than_Or_Equal()
  152. {
  153.     return Bignum_Compare() <= 0;
  154. }
  155.  
  156.  
  157.  
  158. Public Boolean Bignum_Greater_Than_Or_Equal()
  159. {
  160.     return Bignum_Compare() >= 0;
  161. }
  162.  
  163.  
  164.  
  165. Private Short Bignum_Compare()
  166. {
  167.     Bignum_Subtract();
  168.     return Number_Sign( Value_Register );
  169. }
  170.  
  171.  
  172.  
  173.  
  174. /* BIGNUM ADDITION */
  175.  
  176. Public void Bignum_Add()
  177. {
  178.     Integer    size1 = Get_Number_Length( Top(1) );
  179.     Integer    size2 = Get_Number_Length( Top(2) );
  180.     Integer newsize;
  181.     Integer    accumulator;
  182.     Integer index;
  183.     Short    carry;
  184.  
  185.     Object    top1, top2;
  186.  
  187.     /* Compute number of digits in result */
  188.  
  189.     newsize = size1 > size2 ? size1+1 : size2+1;
  190.  
  191.     Make_Bignum_Number( newsize );
  192.     top1 = Top(1);
  193.     top2 = Top(2);
  194.  
  195.     carry = 0;
  196.     for ( index = 0; index < newsize; index++ )
  197.     {
  198.         accumulator = (Integer) carry +
  199.             (index < size1 ? Integer_Digit( top1 , index ) : 0) +
  200.             (index < size2 ? Integer_Digit( top2 , index ) : 0);
  201.         Get_Number_Digit(Value_Register, index) = Low_16( accumulator );
  202.         carry = High_16( accumulator );
  203.     }
  204.     Delete_Leading_Zeros( Value_Register );
  205. }
  206.  
  207. /* BIGNUM SUBTRACTION */
  208.  
  209.  
  210. Public void Bignum_Subtract()
  211. {
  212.     Integer    size1 = Get_Number_Length( Top(1) );
  213.     Integer    size2 = Get_Number_Length( Top(2) );
  214.     Integer newsize;
  215.     Integer    accumulator;
  216.     Integer index;
  217.     Short    carry;
  218.  
  219.     Object    top1, top2;
  220.  
  221.     /* Compute number of digits in result */
  222.  
  223.     newsize = size1 > size2 ? size1+1 : size2+1;
  224.  
  225.     Make_Bignum_Number( newsize );
  226.     top1 = Top(1);
  227.     top2 = Top(2);
  228.  
  229.     carry = 0;
  230.     for ( index = 0; index < newsize; index++ )
  231.     {
  232.         accumulator = (Integer) carry -
  233.             (index < size1 ? Integer_Digit( top1 , index ) : 0) +
  234.             (index < size2 ? Integer_Digit( top2 , index ) : 0);
  235.         Get_Number_Digit(Value_Register, index) = Low_16( accumulator );
  236.         carry = High_16( accumulator );
  237.     }
  238.     Delete_Leading_Zeros( Value_Register );
  239. }
  240.  
  241. /* BIGNUM MULTIPLICATION  */
  242.  
  243.  
  244. Public void Bignum_Multiply()
  245. {
  246.     Integer    size1 = Get_Number_Length( Top(1) );
  247.     Integer    size2 = Get_Number_Length( Top(2) );
  248.     Integer newsize;
  249.     Integer    accumulator;
  250.     Integer index1, index2;
  251.     Short    carry;
  252.  
  253.     Object    top1, top2;
  254.  
  255.     /* Compute number of digits in result */
  256.  
  257.     newsize = size1 + size2;
  258.     if ( abs( (Integer) Most_Significant_Digit(Top(1)) *
  259.         (Integer) Most_Significant_Digit(Top(2)) ) <= MAX_DIGIT )
  260.     {
  261.         newsize--;
  262.     }
  263.  
  264.     Make_Bignum_Number( newsize );
  265.     top1 = Top(1);
  266.     top2 = Top(2);
  267.  
  268.     for ( index1 = 0; index1 < size1; index1 ++ )
  269.     {
  270.         carry = 0;
  271.         for ( index2 = 0; index2 < size2; index2 ++ )
  272.         {
  273.             accumulator = (Integer) carry +
  274.                 Integer_Digit( top1 , index1 ) *
  275.                 Integer_Digit( top2 , index2 ) +
  276.                 Integer_Digit( Value_Register , index1+index2 );
  277.             Get_Number_Digit(Value_Register , index1+index2) =
  278.                 Low_16( accumulator );
  279.             carry = High_16( accumulator );
  280.         }
  281.         if ( index1 + index2 < newsize )
  282.         {
  283.             Get_Number_Digit(Value_Register, index1+index2) = carry;
  284.         }
  285.     }
  286.  
  287.     Delete_Leading_Zeros( Value_Register );
  288. }
  289.  
  290.  
  291. /* BIGNUM DIVISION. */
  292.       
  293. #define QUOTIENT        Top( 1 )
  294. #define DENOMINATOR     Top( 2 )
  295. #define NUMERATOR       Top( 3 )
  296.  
  297. Private Boolean Numerator_Less_Than_Denominator()
  298.  
  299. {
  300.     Boolean result;
  301.  
  302.                                         /* Stack: Q, D, N, d, n...   */
  303.         Push( Top(3) );                 /* Stack: N, Q, D, N, d, n...   */
  304.         Bignum_Abs();
  305.         Pop(1);                         /* Stack: Q, D, N, d, n...   */
  306.         Push(Value_Register);           /* Stack: |N|, Q, D, N, d, n...   */
  307.         Push( Top(3) );                 /* Stack: D, |N|, Q, D, N, d, n...   */
  308.     result = Bignum_Less_Than();     /* compare |numerator| < denominator */
  309.         Pop(2);                         /* Stack: Q, D, N, d, n...   */
  310.     return result;
  311. }
  312.  
  313. Private void Normalize ()
  314.         
  315.     
  316.         /* First justify remainder (numerator) if it's negative. Then
  317.     justify signs for quotient and remainder based on nsign, and
  318.     dsign. Leave quotient in Value_Register and remainder on top 
  319.     of stack.
  320.     */
  321.  
  322. {
  323.     Integer    dsign = Number_Sign( Top(4) );
  324.     Integer    nsign = Number_Sign( Top(5) );
  325.         
  326.     /* Justify values for quotient and remainder
  327.            if numerator < 0,  then 1: quotient has to be one unit less,
  328.                                    2: remainder += denominator
  329.         */
  330.  
  331.  
  332.         if (Number_Sign( Top(3) ) < 0)    /* Stack: Q, D, N, d, n...   */
  333.     {
  334.         Make_Small_Bignum( -1 );
  335.                 Push( Value_Register );   /* Stack: -1, Q, D, N, d, n...   */
  336.         Bignum_Add(); 
  337.                 Pop( 2 );                 /* Stack: D, N, d, n...   */
  338.                 Push( Value_Register );   /* Stack: Q-1, D, N, d, n...   */
  339.  
  340.  
  341.                 Push( Top(3) );           /* Stack: N, Q-1, D, N, d, n...   */
  342.                 Push( Top(3) );           /* Stack: D, N, Q-1, D, N, d, n... */
  343.         Bignum_Add(); 
  344.                 Pop( 2 );                 /* Stack: Q-1, D, N, d, n...   */
  345.                 Top( 3 ) = Value_Register; /* adjusted remainder(numerator) */
  346.     }
  347.  
  348.     /* now justify the signs for quotient and remainder */
  349.  
  350.     if ( nsign < 0 && dsign < 0) /* must reverse sign of remainder */
  351.         {
  352.                 Make_Small_Bignum( 0 );
  353.                 Push( Value_Register );   /* Stack: 0, Q, D, N, d, n...   */
  354.                 Push( Top(4) );           /* Stack: N, 0, Q, D, N, d, n... */
  355.         Bignum_Subtract();
  356.                 Pop( 2 );                 /* Stack: Q, D, N, d, n... */
  357.                 Top( 3 ) = Value_Register;
  358.     }
  359.     else if ( nsign > 0 && dsign < 0 ) /* must reverse sign of quotient */
  360.     {
  361.         Make_Small_Bignum( 0 );
  362.                 Push( Value_Register );   /* Stack: 0, Q, D, N, d, n... */
  363.                 Push( Top(2) );           /* Stack: Q, 0, Q, D, N, d, n... */
  364.         Bignum_Subtract();
  365.                 Pop(3);                   /* Stack: D, N, d, n... */
  366.                 Push( Value_Register) ;   /* Stack: Q, D, N, d, n... */
  367.     }
  368.     else if ( nsign < 0 && dsign > 0 ) /* reverse signs for both */
  369.     {
  370.         Make_Small_Bignum( 0 );
  371.                 Push( Value_Register );   /* Stack: 0, Q, D, N, d, n...   */
  372.                 Push( Top(4) );           /* Stack: N, 0, Q, D, N, d, n... */
  373.         Bignum_Subtract();
  374.                 Pop( 1 );                 /* Stack: 0, Q, D, N, d, n... */
  375.                 Top( 4 ) = Value_Register;
  376.  
  377.                 Push( Top(2) );           /* Stack: Q, 0, Q, D, N, d, n... */
  378.         Bignum_Subtract();
  379.                 Pop(3);                   /* Stack: D, N, d, n... */
  380.                 Push( Value_Register) ;   /* Stack: Q, D, N, d, n... */
  381.     }
  382.         Value_Register = Top( 1 );
  383.         Pop( 2 );
  384.  
  385. }
  386.  
  387.  
  388.  
  389. Public void Bignum_Divide()
  390. {
  391.     Make_Rational_Number();
  392. }
  393.  
  394.  
  395.  
  396. Public    void Long_Division()
  397.         /* Value_Register = Top(1) / Top(2)  */
  398.         /* Push( Top(1) % Top(2) )           */
  399.  
  400. {
  401.         Integer dsize = Get_Number_Length( Top(1) );
  402.     Integer    nsize = Get_Number_Length( Top(2) );
  403.     Integer    dsign = Number_Sign( Top(1) );
  404.     Integer    nsign = Number_Sign( Top(2) );
  405.         Integer accumulator, first_digit;
  406.         Short   index, start_index, first_denominator_digit, carry;
  407.  
  408.  
  409.     
  410.     Push( Copy_Object( Top(2), Bignum_Size(nsize))); /* copied numerator */
  411.     if ( nsign < 0 )  /* if numerator < 0, make it positive */    
  412.     {
  413.         Bignum_Abs(); 
  414.         Pop(1);
  415.         Push( Value_Register );
  416.     }
  417.  
  418.     Push( Copy_Object( Top(2), Bignum_Size(dsize)));/*copied denominator */
  419.     if ( dsign < 0 ) /* if denominator < 0, make it positive */
  420.     {
  421.         Bignum_Abs();
  422.         Pop(1);
  423.         Push( Value_Register );
  424.     }
  425.         
  426.     Make_Bignum_Number( nsize );
  427.     Push( Value_Register );            /* zero-initialized quotient */
  428.  
  429.     
  430.         first_denominator_digit = Most_Significant_Digit( DENOMINATOR );
  431.     
  432.     /* Just divide their absolute values, then manipulate signs for
  433.         quotient and remainder later */
  434.  
  435.     while (TRUE)
  436.     {
  437.         accumulator = 0;
  438.                 index = Get_Number_Length(NUMERATOR) - 1;
  439.         while (abs(accumulator) < abs(first_denominator_digit) &&
  440.                                                       index >= 0)
  441.         {
  442.             accumulator *= RADIX;
  443.                         accumulator += Integer_Digit(NUMERATOR,index);
  444.             index--;
  445.         }
  446.  
  447.         first_digit = accumulator / first_denominator_digit;
  448.  
  449.         start_index = index + 1 - (dsize - 1);
  450.  
  451.         if (start_index < 0)
  452.         {
  453.                         Delete_Leading_Zeros( QUOTIENT );
  454.                         Normalize();
  455.             return;
  456.         }
  457.  
  458.                 Get_Number_Digit(QUOTIENT,start_index ) += Low_16(first_digit);
  459.         
  460.         carry = 0;
  461.  
  462.         for ( index = 0; index < dsize; index++ )
  463.         {
  464.             accumulator = - first_digit *
  465.                             Get_Number_Digit(DENOMINATOR,index) +
  466.                 carry + 
  467.                             Get_Number_Digit(NUMERATOR,index + start_index);
  468.  
  469.                         Get_Number_Digit(NUMERATOR, index + start_index) =
  470.                 Low_16( accumulator );
  471.             carry = High_16( accumulator );
  472.  
  473.         }
  474.  
  475.         if (index + start_index < nsize)
  476.         {
  477.                         Get_Number_Digit(NUMERATOR,index+start_index) += carry;
  478.         }
  479.  
  480.                 Delete_Leading_Zeros( NUMERATOR );
  481.  
  482.                 if ((start_index == 0) && Numerator_Less_Than_Denominator())
  483.         {
  484.                         Delete_Leading_Zeros( QUOTIENT );
  485.                         Normalize();
  486.             return;
  487.         }
  488.     }
  489.  
  490. }
  491.  
  492.  
  493.  
  494. Private void Delete_Leading_Zeros( num )
  495.  
  496.     Object num;
  497. {
  498.     /*
  499.        Leading zeros occur in two ways: an explicit leading digit of zero,
  500.        and a leading one (or minus one) followed by a digit of opposite
  501.        sign, ie "-1,5" == "-5".
  502.     */
  503.  
  504.     Short    index = Get_Number_Length(num) - 1;
  505.     Integer    accumulator;
  506.     Short    first_digit;
  507.  
  508.     while (index >= 1)
  509.     {
  510.         if (abs( first_digit = Get_Number_Digit(num,index) ) > 1)
  511.             break;
  512.         if (abs ( accumulator = first_digit * RADIX +
  513.             Get_Number_Digit(num,index-1) ) > MAX_DIGIT)
  514.             break;
  515.         else
  516.         {
  517.             Get_Number_Length(num) = (Integer) index;
  518.             Get_Number_Digit(num,index-1) = Low_16( accumulator );
  519.             index--;
  520.         }
  521.     }
  522. }
  523.  
  524.  
  525.  
  526.  
  527. Public void Bignum_Quotient()
  528. {
  529.     Long_Division();
  530.     Pop(1);     /* popping remainder from stack */
  531. }
  532.  
  533.  
  534.  
  535. Public void Bignum_Remainder()
  536. {
  537.     Long_Division();
  538.     Value_Register = Top(1);
  539.     Pop(1);
  540. }
  541.  
  542.  
  543.  
  544. Public void Bignum_Modulo()
  545. {
  546.     Integer    dsign = Number_Sign( Top(1) ); 
  547.     Integer    nsign = Number_Sign( Top(2) );
  548.     
  549.     Long_Division();
  550.     Value_Register = Top(1);
  551.  
  552.     if ( (nsign * dsign) < 0 )
  553.         /* == "if ((nsign > 0 && dsign < 0) || (nsign < 0 && dsign > 0))"  */
  554.     {
  555.         Push( Top(2) ); /* denominator */
  556.         Bignum_Add(); /* remainder + denominator */
  557.         Pop( 1 );
  558.     }
  559.     
  560.     Pop(1);
  561. }
  562.  
  563.  
  564.  
  565. Public void Bignum_Negate()
  566. {
  567.     Integer len = Get_Number_Length( Top( 1 ) );
  568.     Integer index;
  569.  
  570.     Value_Register = Copy_Object( Top( 1 ) , Bignum_Size( len ) );
  571.     for ( index = 0; index < len; index++ )
  572.     {
  573.         Get_Number_Digit( Value_Register , index ) =
  574.             - Get_Number_Digit( Value_Register , index );
  575.     }
  576. }
  577.  
  578.  
  579.  
  580. Public void Bignum_Abs()
  581. {
  582.     if (Is_Bignum_Negative())
  583.     {
  584.         Bignum_Negate();
  585.     }
  586.     else
  587.     {
  588.         Value_Register = Top(1);
  589.     }
  590. }
  591.  
  592.  
  593.  
  594. Public void Bignum_Numerator()
  595. {
  596.     Value_Register = Top(1);
  597. }
  598.  
  599.  
  600.  
  601. Public void Bignum_Denominator()
  602. {
  603.     Make_Small_Bignum(1);
  604. }
  605.  
  606.  
  607.  
  608. Public void Bignum_Rationalize()
  609. {
  610.     Error("Bignum_Rationalize not yet implemented!");
  611. }
  612.  
  613.  
  614.  
  615. Public void Bignum_Max()
  616. {
  617.     Value_Register = Bignum_Greater_Than() ? Top(2) : Top(1);
  618. }
  619.  
  620.  
  621.  
  622. Public void Bignum_Min()
  623. {
  624.     Value_Register = Bignum_Less_Than() ? Top(2) : Top(1);
  625. }
  626.  
  627.  
  628.  
  629. Public void Bignum_GCD()
  630. {
  631.     /* make arguments positive since gcd is positive */
  632.  
  633.     Push( Top(2) );
  634.     Push( Top(2) );
  635.  
  636.     Bignum_Abs();
  637.     Replace(1, Value_Register);
  638.  
  639.     Push(Top(2));
  640.     Bignum_Abs();
  641.     Replace(1, Value_Register);
  642.  
  643.     while (Number_Sign(Top(1)) != 0)
  644.     {
  645.         Bignum_Remainder();
  646.         Top(2) = Top(1);
  647.         Top(1) = Value_Register;
  648.     }
  649.  
  650.     Value_Register = Top(2);
  651.     
  652.     Pop(3);
  653. }
  654.  
  655.  
  656.  
  657. Public void Bignum_LCM()
  658. {
  659.     /* LCM(a,b) = (a*b)/GCD(a,b)  */
  660.     
  661.     Bignum_Multiply();
  662.     Push(Value_Register);
  663.  
  664.     Push(Top(3));
  665.     Push(Top(3));
  666.  
  667.     Bignum_GCD();
  668.     Push(Value_Register);
  669.  
  670.     Top(2) = Top(4);
  671.     Number_Divide();
  672.  
  673.     Push(Value_Register);
  674.     Number_Abs();
  675.  
  676.     Pop(5);
  677. }
  678.  
  679.  
  680.  
  681.  
  682. Public void Bignum_Floor()
  683. {
  684.     Value_Register = Top(1);
  685. }
  686.  
  687.  
  688.  
  689. Public void Bignum_Ceiling()
  690. {
  691.     Value_Register = Top(1);
  692. }
  693.  
  694.  
  695.  
  696. Public void Bignum_Truncate()
  697. {
  698.     Value_Register = Top(1);
  699. }
  700.  
  701.  
  702.  
  703. Public void Bignum_Round()
  704. {
  705.     Value_Register = Top(1);
  706. }
  707.  
  708.  
  709.  
  710.  
  711. Public void Bignum_Sqrt()
  712. {
  713.     if(Number_Sign(Top(1)) < 0)
  714.     {
  715.         Error("Argument to sqrt must be nonnegative");
  716.     }
  717.  
  718.     Promote(1, REAL_LEVEL);
  719.  
  720.     Make_Real_Number( sqrt (Get_Number_Real_Value(Top(1))) );
  721. }
  722.  
  723.  
  724.  
  725. Public void Bignum_Exp()
  726. {
  727.     Promote(1, REAL_LEVEL);
  728.  
  729.     Make_Real_Number( exp (Get_Number_Real_Value(Top(1))) );
  730. }
  731.  
  732.  
  733.  
  734. Public void Bignum_Log()
  735. {
  736.     if(Number_Sign(Top(1)) <= 0)
  737.     {
  738.         Error("Argument of log must be positive");
  739.     }
  740.  
  741.  
  742.     Promote(1, REAL_LEVEL);
  743.  
  744.     Make_Real_Number( log (Get_Number_Real_Value(Top(1))) );
  745. }
  746.  
  747.  
  748.  
  749. Public void Bignum_Expt()
  750. {
  751.     Push( Top(2) );
  752.     Is_Number_Negative();
  753.     Pop(1);
  754.  
  755.     if( (Number_Sign(Top(1)) == 0) && (Value_Register == The_True_Object) )
  756.     {
  757.  
  758.         Error("Domain error for expt");
  759.     }
  760.  
  761.     else if (Number_Sign(Top(1)) >= 0)
  762.     {
  763.         Make_Small_Bignum( 1 ); /* running total (initially = 1) */
  764.  
  765.         while ( Number_Sign(Top(1)) > 0 )
  766.         {
  767.             Push( Value_Register );        /* running total */
  768.  
  769.             Push( Top(2) );
  770.             Make_Small_Bignum( 1 );
  771.             Push( Value_Register );
  772.             Number_Subtract();
  773.             Pop(2);
  774.             Replace(2,Value_Register);    /* exponent -= 1 */
  775.  
  776.             Push( Top(3) );            /* total *= mantissa */
  777.             Bignum_Multiply();
  778.             Pop( 2 );
  779.         }
  780.     }
  781.     else
  782.     {
  783.         /* Negative Exponent */
  784.  
  785.         Promote(1, REAL_LEVEL);
  786.         Promote(2, REAL_LEVEL);
  787.  
  788.         Make_Real_Number( pow ( (Get_Number_Real_Value(Top(2))),
  789.                 (Get_Number_Real_Value(Top(1))) ) );
  790.     }
  791. }
  792.  
  793.  
  794.  
  795.  
  796. Public void Bignum_Sin()
  797. {
  798.     Promote(1, REAL_LEVEL);
  799.  
  800.     Make_Real_Number( sin (Get_Number_Real_Value(Top(1))) );
  801. }
  802.  
  803.  
  804.  
  805. Public void Bignum_Cos()
  806. {
  807.     Promote(1, REAL_LEVEL);
  808.  
  809.     Make_Real_Number( cos (Get_Number_Real_Value(Top(1))) );
  810. }
  811.  
  812.  
  813.  
  814. Public void Bignum_Tan()
  815. {
  816.     Promote(1, REAL_LEVEL);
  817.  
  818.     Make_Real_Number( tan (Get_Number_Real_Value(Top(1))) );
  819. }
  820.  
  821.  
  822.  
  823. Public void Bignum_Asin()
  824. {
  825.     Error("Argument of asin must lie between -1 and 1, inclusive");
  826. }
  827.  
  828.  
  829.  
  830. Public void Bignum_Acos()
  831. {
  832.     Error("Argument of acos must lie between -1 and 1, inclusive");
  833. }
  834.  
  835.  
  836.  
  837. Public void Bignum_Atan()
  838. {
  839.     Promote(1, REAL_LEVEL);
  840.  
  841.     Make_Real_Number( atan (Get_Number_Real_Value(Top(1))) );
  842. }
  843.  
  844.  
  845.  
  846. Public void Bignum_Atan2()
  847. {
  848.     Promote(1, REAL_LEVEL);
  849.     Promote(2, REAL_LEVEL);
  850.  
  851.     Make_Real_Number( atan2 (Get_Number_Real_Value(Top(2)), 
  852.                     Get_Number_Real_Value(Top(1))) );
  853. }
  854.  
  855.  
  856.  
  857.  
  858. /* Transfer functions */
  859.  
  860.  
  861. Public void Bignum_Exact_To_Inexact()
  862. {
  863.     Promote( 1 , REAL_LEVEL );
  864.     Value_Register = Top(1);
  865. }
  866.  
  867.  
  868.  
  869. Public void Bignum_Inexact_To_Exact()
  870. {
  871.     Value_Register = Top(1);
  872. }
  873.  
  874. /* BIGNUM TO STRING */
  875.  
  876. Public void Bignum_To_String()
  877.  
  878. {
  879.     Import void String_Append();
  880.  
  881.     Integer    high, low;
  882.     Object    remainder;
  883.     Character partial_string[MAX_CHARS_PER_INT];
  884.     Integer    radix = Number_To_Integer( Top(1) );
  885.     Integer print_radix = 0;
  886.     Object    num = Top(2) ;
  887.  
  888.     switch ( Get_Number_Length( num ) )
  889.     {
  890.     case 0:
  891.         sprintf( partial_string , "%d" , 0 );
  892.         Make_Constant_String( partial_string );
  893.         return;
  894.  
  895.     case 1:
  896.         if ( radix == 10 )
  897.         {
  898.             sprintf( partial_string, "%d", Get_Number_Digit(num,0));
  899.             Make_Constant_String( partial_string );
  900.         }
  901.         else
  902.         {
  903.             Make_Constant_String(
  904.                Integer_To_Cstring( Get_Number_Digit(num,0), 
  905.                         partial_string, radix, 0) );
  906.         }
  907.         return;
  908.         
  909.     case 2:
  910.         if ( radix == 10 )
  911.         {
  912.             sprintf( partial_string , "%d" ,
  913.                     Get_Number_Digit(num,1) * RADIX +
  914.                     Get_Number_Digit(num,0));
  915.             Make_Constant_String( partial_string );
  916.         }
  917.         else
  918.         {
  919.             Make_Constant_String(
  920.                 Integer_To_Cstring((Integer)
  921.                            Get_Number_Digit(num,1) * RADIX +
  922.                            Get_Number_Digit(num,0), 
  923.                         partial_string, radix, 0) );
  924.         }
  925.         return;
  926.  
  927.     default:
  928.         print_radix =    radix == 2  ? 16 :
  929.                 radix == 8  ? 4096 :
  930.                 radix == 10 ? 10000 :
  931.                 radix == 16 ? 65536 : 10000;
  932.  
  933.         Make_Constant_String( "" );
  934.         Push( Value_Register );
  935.         Push( Top( 3 ) ); 
  936.         do {
  937.             Integer_To_Bignum( print_radix );
  938.             Push( Value_Register );
  939.             Long_Division();
  940.             remainder = Top(1);
  941.             Pop(3); /* remainder, print_radix and dividend */
  942.             high = Get_Number_Length( remainder ) == 2
  943.                 ? Get_Number_Digit( remainder , 1)
  944.                 : 0;
  945.             low = Get_Number_Digit( remainder , 0 );
  946.  
  947.             Push( Value_Register );    /* new dividend = quotient */
  948.             
  949.             Make_Constant_String( 
  950.                 Integer_To_Cstring( abs(high * RADIX + low),
  951.                             partial_string, radix, 4) );
  952.             Push( Value_Register );
  953.             Push( Top( 3 ) );
  954.             String_Append(); Pop( 2 );
  955.             Replace( 2 , Value_Register );    
  956.         } while ( Get_Number_Length( Top( 1 ) ) > 2);
  957.         
  958.         Integer_To_Number( radix );
  959.         Push( Value_Register );
  960.         Number_To_String(); Pop( 2 );
  961.         Push( Value_Register );
  962.         Push( Top( 2 ) );
  963.         String_Append(); Pop( 3 );
  964.     }
  965. }
  966.  
  967. Public void Bignum_Make_Rectangular()
  968. {
  969.     Promote(2, REAL_LEVEL);
  970.     Promote(1, REAL_LEVEL);
  971.  
  972.     Make_Complex_Number( Get_Number_Real_Value(Top(2)),
  973.                 Get_Number_Real_Value(Top(1)) );
  974.  
  975. }
  976.  
  977.  
  978.  
  979. Public void Bignum_Make_Polar()
  980.  
  981. #define MAG Get_Number_Real_Value(Top(2))
  982. #define ANG Get_Number_Real_Value(Top(1))
  983.  
  984. {
  985.     Promote( 2, REAL_LEVEL);
  986.     Promote( 1, REAL_LEVEL);
  987.  
  988.     Make_Complex_Number( (MAG) * cos(ANG) , (MAG) * sin(ANG) );
  989.  
  990. }
  991.  
  992. #undef MAG
  993. #undef ANG
  994.  
  995.  
  996.  
  997. Public void Bignum_Real_Part()
  998. {
  999.     Value_Register = Top(1);
  1000. }
  1001.  
  1002.  
  1003.  
  1004. Public void Bignum_Imaginary_Part()
  1005. {
  1006.     Make_Real_Number(0.0);
  1007. }
  1008.  
  1009.  
  1010.  
  1011. Public void Bignum_Magnitude()
  1012. {
  1013.     Bignum_Abs();
  1014. }
  1015.  
  1016.  
  1017.  
  1018. Public void Bignum_Angle()
  1019. {
  1020.     Make_Real_Number(0.0);
  1021. }
  1022.  
  1023.  
  1024.  
  1025.  
  1026.  
  1027. /* OTHER CONVERSIONS INVOLVING BIGNUMS */
  1028.  
  1029.  
  1030. Public void Make_Small_Bignum(num)
  1031.  
  1032.     Integer num;
  1033. {
  1034.     Integer_To_Bignum( num );
  1035. }
  1036.  
  1037.  
  1038.  
  1039. Public Integer Bignum_To_Integer(num)
  1040.  
  1041.     Object num;
  1042. {
  1043.     switch (Get_Number_Length(num))
  1044.     {
  1045.     case 0:
  1046.         return( 0 );
  1047.  
  1048.     case 1:
  1049.         return( Integer_Digit(num,0) );
  1050.  
  1051.     case 2:
  1052.         return( Integer_Digit(num,1) * RADIX + Integer_Digit(num,0) );
  1053.  
  1054.     default:
  1055.         Display_Error("Implementation Restriction; integer too large:", 
  1056.                 num);
  1057.         return( 0 );
  1058.     }
  1059. }
  1060.  
  1061.  
  1062.  
  1063. Public void Integer_To_Bignum(num)
  1064.  
  1065.     Integer num;
  1066. {
  1067.     if (num == 0)
  1068.     {
  1069.         Make_Bignum_Number(1);
  1070.     }
  1071.     else if (abs(num) < RADIX)
  1072.     {
  1073.         Make_Bignum_Number(1);
  1074.         Get_Number_Digit(Value_Register,0) = num;
  1075.     }
  1076.     else
  1077.     {
  1078.         Make_Bignum_Number(2);
  1079.         Get_Number_Digit(Value_Register,0) = Low_16(num);
  1080.         Get_Number_Digit(Value_Register,1) = High_16(num);
  1081.     }
  1082. }
  1083.  
  1084.  
  1085.  
  1086. /* Bignum Diagnostics */
  1087.  
  1088. /*
  1089.  
  1090. Private void Shownum( title , num )
  1091.  
  1092.     String title;
  1093.     Object num ;
  1094. {
  1095.     if ( Is_String(num) )
  1096.     {
  1097.         printf( "%s: <string \"%s\">" , title , Get_String_Value(num));
  1098.         return;
  1099.     }
  1100.  
  1101.     if ( Is_Number( num ) && Get_Number_Tower_Position(num) == REAL_LEVEL )
  1102.     {
  1103.         printf( "%s: <real %f>" , title , Get_Number_Real_Value(num));
  1104.         return;
  1105.     }
  1106.     if ( ! Is_Number(num) || Get_Number_Tower_Position(num) != BIGNUM_LEVEL)
  1107.     {
  1108.         printf( "%s: <NOT A BIGNUM>" , title );
  1109.     }
  1110.     else
  1111.     {
  1112.         Integer index;
  1113.         Integer len = Get_Number_Length(num);
  1114.  
  1115.         printf( "%s: { %d:" , title ,  len );
  1116.         for ( index = 0; index < len; index ++ )
  1117.         {
  1118.             printf( " %d" , Get_Number_Digit(num,index) );
  1119.         }
  1120.  
  1121.         printf( "}" );
  1122.     }
  1123. }
  1124. */
  1125.