Loading ...
Sorry, an error occurred while loading the content.

Re: [PrimeNumbers] big numbers library

Expand Messages
  • Alan Eliasen
    ... I need to clarify that Sun s JVM hasn t used Colin Plumb s library since version 1.2. Since then, BigInteger has been implented in pure Java. If you use
    Message 1 of 9 , Aug 5 8:51 AM
    • 0 Attachment
      Jan van Oort wrote:
      > 2) take Colin Plum's source code, study it closely, and use to implement
      > your own method in a shared library ( .so or .dll compiled from C/C++ ).
      > Probably closely related to 1)
      > 3) download the sources of java.math.BigInteger and see if you can learn
      > anything from it, i.e. from the non-native ( Java ) part.
      > 4) look on the internet --- developer's forums etc --- if somebody has
      > already had the same idea / need as you, and developed something
      > 5) contact Colin Plum and ask him directly.

      I need to clarify that Sun's JVM hasn't used Colin Plumb's library
      since version 1.2. Since then, BigInteger has been implented in pure Java.

      If you use the free Kaffe JVM, it can be compiled to use the GMP
      library for BigInteger. You need to both compile with this and enable
      it at runtime with a command-line switch. Still, there's no API to have
      BigInteger exponents.

      In any case, BigInteger represents its bits as an int[] array. This
      limits the size of the numbers that can be represented to about
      68 billion digits, or possibly less.

      But Sun's algorithms are horrible--they only use the most naive
      O(n^2) algorithm for multiplication, and equally horrible algorithms for
      radix conversion and exponentiation, so your program would be horribly
      time-bound. For example, it takes about 16 hours just to convert one of
      the larger Mersenne numbers, about 2^13000000, (which is *way, way*
      smaller than the 2^2147483647 limit that you're complaining about) to
      decimal on my computer. The exponentiation takes horribly long unless
      you write your own bit-shifting algorithms to fix Sun's inadequacies too.

      In short, if you're going to use numbers that big, you're going to
      have to write your own library. Or try Kaffe. NB: make sure you
      compile Kaffe with the option that intermediate numbers are allocated on
      the heap, not the stack, 'cause your stack isn't gigabytes in size.

      --
      Alan Eliasen | "It is not enough to do your best;
      eliasen@... | you must know what to do and THEN
      http://futureboy.homeip.net/ | do your best." -- W. Edwards Deming
    • Jan van Oort
      Alan, you are quite right. Anyway, if I were in Faysal s case, it probably would boil down - and that rather quickly - to option 1, with an eye on option 2.
      Message 2 of 9 , Aug 5 10:57 AM
      • 0 Attachment
        Alan,
        you are quite right. Anyway, if I were in Faysal's case, it probably would
        boil down - and that rather quickly - to option 1, with an eye on option 2.
        The next time I am in between two project, I am going to write a
        BigInteger.pow( BigInteger _exponent ) method. Just for fun. On a rainy day.
        :-D
        Jan
        PS I was not complaining about any limits. Faysal was.

        On 8/5/05, Alan Eliasen <eliasen@...> wrote:
        >
        > Jan van Oort wrote:
        > > 2) take Colin Plum's source code, study it closely, and use to implement
        > > your own method in a shared library ( .so or .dll compiled from C/C++ ).
        > > Probably closely related to 1)
        > > 3) download the sources of java.math.BigInteger and see if you can learn
        > > anything from it, i.e. from the non-native ( Java ) part.
        > > 4) look on the internet --- developer's forums etc --- if somebody has
        > > already had the same idea / need as you, and developed something
        > > 5) contact Colin Plum and ask him directly.
        >
        > I need to clarify that Sun's JVM hasn't used Colin Plumb's library
        > since version 1.2. Since then, BigInteger has been implented in pure Java.
        >
        > If you use the free Kaffe JVM, it can be compiled to use the GMP
        > library for BigInteger. You need to both compile with this and enable
        > it at runtime with a command-line switch. Still, there's no API to have
        > BigInteger exponents.
        >
        > In any case, BigInteger represents its bits as an int[] array. This
        > limits the size of the numbers that can be represented to about
        > 68 billion digits, or possibly less.
        >
        > But Sun's algorithms are horrible--they only use the most naive
        > O(n^2) algorithm for multiplication, and equally horrible algorithms for
        > radix conversion and exponentiation, so your program would be horribly
        > time-bound. For example, it takes about 16 hours just to convert one of
        > the larger Mersenne numbers, about 2^13000000, (which is *way, way*
        > smaller than the 2^2147483647 limit that you're complaining about) to
        > decimal on my computer. The exponentiation takes horribly long unless
        > you write your own bit-shifting algorithms to fix Sun's inadequacies too.
        >
        > In short, if you're going to use numbers that big, you're going to
        > have to write your own library. Or try Kaffe. NB: make sure you
        > compile Kaffe with the option that intermediate numbers are allocated on
        > the heap, not the stack, 'cause your stack isn't gigabytes in size.
        >
        > --
        > Alan Eliasen | "It is not enough to do your best;
        > eliasen@... | you must know what to do and THEN
        > http://futureboy.homeip.net/ | do your best." -- W. Edwards Deming
        >



        --

        Non sunt multiplicanda entia praeter necessitatem


        [Non-text portions of this message have been removed]
      • Alan Eliasen
        ... That s because Sun s Java implementation still uses horrible O(n^2) algorithms for multiplication. Their exponentiation routine already does
        Message 3 of 9 , Aug 7 5:34 AM
        • 0 Attachment
          fyatim wrote:
          > I wrote a small method using a well known algorithm “Exponentiation by
          > Squaring”, but it still take horrible execution time.

          That's because Sun's Java implementation still uses horrible O(n^2)
          algorithms for multiplication. Their exponentiation routine already
          does exponentiation by squaring, so you probably can't improve on it
          without fixing multiplication.

          > Where can I find the algorithm you are mentioning i.e. “bit shifting” ??

          "Bit shifting" works when your base contains powers of 2. This is
          because you can do powers of 2 by simply left-shifting the binary
          representation by the appropriate number of bits. If you're doing
          something like calculating large Mersenne numbers, this makes it about a
          thousand times faster or more than Sun's implementation. It's an easy
          and obvious optimization that Sun missed.

          In short, here's a code snippet that does it. The base is expected
          to be in a BigInteger called "big", and the exponent in an int called
          "exponent". It factors out powers of two quickly by the call to
          getLowestSetBit(), and does the exponentiation for powers of two rapidly
          with shiftLeft() and then multiplies it by the remaining part that isn't
          a power of 2.

          This only helps if your base contains powers of 2.

          if (big.signum() > 0)
          {
          // Get factor of two
          int bit = big.getLowestSetBit();

          if (bit > 0)
          {
          big = big.shiftRight(bit);
          BigInteger twoPower = FrinkBigInteger.ONE.shiftLeft(bit*exponent);
          if (big.equals(FrinkBigInteger.ONE))
          return FrinkInteger.construct(twoPower);
          else
          {
          big = big.pow(exponent);
          return FrinkInteger.construct(big.multiply(twoPower));
          }
          }
          }

          --
          Alan Eliasen | "It is not enough to do your best;
          eliasen@... | you must know what to do and THEN
          http://futureboy.homeip.net/ | do your best." -- W. Edwards Deming
        • Alan Eliasen
          If it wasn t clear (and it wasn t,) the algorithm I just posted was one to speed up exponentiation. I use it as a wrapper around BigInteger.pow(BigInteger
          Message 4 of 9 , Aug 7 5:39 AM
          • 0 Attachment
            If it wasn't clear (and it wasn't,) the algorithm I just posted was
            one to speed up exponentiation. I use it as a wrapper around
            BigInteger.pow(BigInteger big, int exponent) in Java.

            --
            Alan Eliasen | "It is not enough to do your best;
            eliasen@... | you must know what to do and THEN
            http://futureboy.homeip.net/ | do your best." -- W. Edwards Deming
          • fyatim
            Jan, Alan, Thank you for your support. I wrote a small method using a well known algorithm Exponentiation by Squaring , but it still take horrible execution
            Message 5 of 9 , Aug 20 4:19 AM
            • 0 Attachment
              Jan, Alan,

              Thank you for your support.

              I wrote a small method using a well known algorithm "Exponentiation by
              Squaring", but it still take horrible execution time.

              Where can I find the algorithm you are mentioning i.e. "bit shifting" ??

              Faysal





              _____

              From: primenumbers@yahoogroups.com [mailto:primenumbers@yahoogroups.com] On
              Behalf Of Jan van Oort
              Sent: Friday, August 05, 2005 8:57 PM
              To: Alan Eliasen
              Cc: Prime Number
              Subject: Re: [PrimeNumbers] big numbers library



              Alan,
              you are quite right. Anyway, if I were in Faysal's case, it probably would
              boil down - and that rather quickly - to option 1, with an eye on option 2.
              The next time I am in between two project, I am going to write a
              BigInteger.pow( BigInteger _exponent ) method. Just for fun. On a rainy day.

              :-D
              Jan
              PS I was not complaining about any limits. Faysal was.

              On 8/5/05, Alan Eliasen <eliasen@...> wrote:
              >
              > Jan van Oort wrote:
              > > 2) take Colin Plum's source code, study it closely, and use to implement
              > > your own method in a shared library ( .so or .dll compiled from C/C++ ).
              > > Probably closely related to 1)
              > > 3) download the sources of java.math.BigInteger and see if you can learn
              > > anything from it, i.e. from the non-native ( Java ) part.
              > > 4) look on the internet --- developer's forums etc --- if somebody has
              > > already had the same idea / need as you, and developed something
              > > 5) contact Colin Plum and ask him directly.
              >
              > I need to clarify that Sun's JVM hasn't used Colin Plumb's library
              > since version 1.2. Since then, BigInteger has been implented in pure Java.
              >
              > If you use the free Kaffe JVM, it can be compiled to use the GMP
              > library for BigInteger. You need to both compile with this and enable
              > it at runtime with a command-line switch. Still, there's no API to have
              > BigInteger exponents.
              >
              > In any case, BigInteger represents its bits as an int[] array. This
              > limits the size of the numbers that can be represented to about
              > 68 billion digits, or possibly less.
              >
              > But Sun's algorithms are horrible--they only use the most naive
              > O(n^2) algorithm for multiplication, and equally horrible algorithms for
              > radix conversion and exponentiation, so your program would be horribly
              > time-bound. For example, it takes about 16 hours just to convert one of
              > the larger Mersenne numbers, about 2^13000000, (which is *way, way*
              > smaller than the 2^2147483647 limit that you're complaining about) to
              > decimal on my computer. The exponentiation takes horribly long unless
              > you write your own bit-shifting algorithms to fix Sun's inadequacies too.
              >
              > In short, if you're going to use numbers that big, you're going to
              > have to write your own library. Or try Kaffe. NB: make sure you
              > compile Kaffe with the option that intermediate numbers are allocated on
              > the heap, not the stack, 'cause your stack isn't gigabytes in size.
              >
              > --
              > Alan Eliasen | "It is not enough to do your best;
              > eliasen@... | you must know what to do and THEN
              > http://futureboy.homeip.net/ | do your best." -- W. Edwards Deming
              >



              --

              Non sunt multiplicanda entia praeter necessitatem


              [Non-text portions of this message have been removed]



              Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
              The Prime Pages : http://www.primepages.org/






              SPONSORED LINKS


              Mathematics
              <http://groups.yahoo.com/gads?t=ms&k=Mathematics+and+computer+science&w1=Mat
              hematics+and+computer+science&w2=Music+theory&w3=Theory+of&c=3&s=71&.sig=SOh
              q77_rF4rHyNjUSRWLFg> and computer science

              Music
              <http://groups.yahoo.com/gads?t=ms&k=Music+theory&w1=Mathematics+and+compute
              r+science&w2=Music+theory&w3=Theory+of&c=3&s=71&.sig=6RLtLyQQ5iFfnkmGdOkbBA>
              theory

              Theory
              <http://groups.yahoo.com/gads?t=ms&k=Theory+of&w1=Mathematics+and+computer+s
              cience&w2=Music+theory&w3=Theory+of&c=3&s=71&.sig=O8mFVRYrr9LhUeQJhzbgFg>
              of



              _____

              YAHOO! GROUPS LINKS



              * Visit your group "primenumbers
              <http://groups.yahoo.com/group/primenumbers> " on the web.

              * To unsubscribe from this group, send an email to:
              primenumbers-unsubscribe@yahoogroups.com
              <mailto:primenumbers-unsubscribe@yahoogroups.com?subject=Unsubscribe>

              * Your use of Yahoo! Groups is subject to the Yahoo!
              <http://docs.yahoo.com/info/terms/> Terms of Service.



              _____



              [Non-text portions of this message have been removed]
            • fyatim
              Alan, Yes is clear .. Thanks. But, my problem still the same when the exponent is a prime 2... I m trying to find out the best (fastest) way to calculate it
              Message 6 of 9 , Aug 21 1:15 AM
              • 0 Attachment
                Alan,
                Yes is clear .. Thanks.
                But, my problem still the same when the exponent is a prime > 2...
                I'm trying to find out the best (fastest) way to calculate it ...
                I welcome any new ideas...
                Regards
                Faysal

                -----Original Message-----
                From: primenumbers@yahoogroups.com [mailto:primenumbers@yahoogroups.com] On
                Behalf Of Alan Eliasen
                Sent: Sunday, August 07, 2005 3:34 PM
                To: fyatim
                Cc: 'Jan van Oort'; 'Prime Number'
                Subject: Re: [PrimeNumbers] big numbers library

                fyatim wrote:
                > I wrote a small method using a well known algorithm "Exponentiation by
                > Squaring", but it still take horrible execution time.

                That's because Sun's Java implementation still uses horrible O(n^2)
                algorithms for multiplication. Their exponentiation routine already
                does exponentiation by squaring, so you probably can't improve on it
                without fixing multiplication.

                > Where can I find the algorithm you are mentioning i.e. "bit shifting" ??

                "Bit shifting" works when your base contains powers of 2. This is
                because you can do powers of 2 by simply left-shifting the binary
                representation by the appropriate number of bits. If you're doing
                something like calculating large Mersenne numbers, this makes it about a
                thousand times faster or more than Sun's implementation. It's an easy
                and obvious optimization that Sun missed.

                In short, here's a code snippet that does it. The base is expected
                to be in a BigInteger called "big", and the exponent in an int called
                "exponent". It factors out powers of two quickly by the call to
                getLowestSetBit(), and does the exponentiation for powers of two rapidly
                with shiftLeft() and then multiplies it by the remaining part that isn't
                a power of 2.

                This only helps if your base contains powers of 2.

                if (big.signum() > 0)
                {
                // Get factor of two
                int bit = big.getLowestSetBit();

                if (bit > 0)
                {
                big = big.shiftRight(bit);
                BigInteger twoPower = FrinkBigInteger.ONE.shiftLeft(bit*exponent);
                if (big.equals(FrinkBigInteger.ONE))
                return FrinkInteger.construct(twoPower);
                else
                {
                big = big.pow(exponent);
                return FrinkInteger.construct(big.multiply(twoPower));
                }
                }
                }

                --
                Alan Eliasen | "It is not enough to do your best;
                eliasen@... | you must know what to do and THEN
                http://futureboy.homeip.net/ | do your best." -- W. Edwards Deming


                Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
                The Prime Pages : http://www.primepages.org/


                Yahoo! Groups Links
              Your message has been successfully submitted and would be delivered to recipients shortly.