Thinking out loud, If there is an FFT implementation, there might be some speedups for integer powers of large integers:
0. In x^y, you would need to compute the transform of x only once; 1. Similarly, the transforms of other powers that are to be reused could be saved; 2. It might be possible to calculate x^3 or x^4 rather than x^2, by taking that power of the transform, if the radix permits (the precision of a double would be the limiting factor). I'm just saying, Henry Rich ---- Roger Hui <[email protected]> wrote: > The repeated squaring still needs a large multiplication > of numbers with each with about 2357207%2 digits. > This alone would take considerable time with the > current non-FFT multiplication. > > The example in the Jwiki essay indicates that > two million-digit numbers would take about 23 seconds. > In contrast: > > timer 'x*y' [ x=: ?10x^e [ y=: ?10x^e=: 1e4 > 0.0486372 > timer 'x*y' [ x=: ?10x^e [ y=: ?10x^e=: 2e4 > 0.286935 > timer 'x*y' [ x=: ?10x^e [ y=: ?10x^e=: 4e4 > 0.882918 > timer 'x*y' [ x=: ?10x^e [ y=: ?10x^e=: 8e4 > 3.2742 > timer 'x*y' [ x=: ?10x^e [ y=: ?10x^e=: 16e4 > 12.9076 > > Looks like doubling the number of digits requires > quadrupling the time, so 1e6 digits would take > about 12.9076*4^3 or 827 or so seconds. > > > > ----- Original Message ----- > From: [email protected] > Date: Wednesday, July 6, 2011 10:18 > Subject: Re: [Jprogramming] Large numbers > To: Programming forum <[email protected]> > Cc: Roger Hui <[email protected]> > > > 0. One of these numbers needs to have an x to get extended > > precision. > > 1. 28433 * 2^7830457 + 1 > > > > is the same as > > > > 28433 * 2^7830458 > > > > which seems unlikely to be what was meant. > > > > 2. Roger, isn't the power done by repeated squaring or > > some such trick? > > So the power will take about 30-50 multiplications whose > > average length^2 is around 1500000^2, right? That > > could give an estimate > > of the expected time. > > > > Henry Rich > > > > ---- Roger Hui <[email protected]> wrote: > > > The multiplication is currently O(n^2) so the number > > > you described will take a very long time. How long? > > > You can gauge it by timing the multiplication of > > > numbers with 1e4, 2e4, 4e4, etc. digits. > > > > > > The multiplication would be faster with: > > > http://www.jsoftware.com/jwiki/Essays/FFT > > > > > > > > > > > > ----- Original Message ----- > > > From: David Vaughan <[email protected]> > > > Date: Wednesday, July 6, 2011 8:32 > > > Subject: [Jprogramming] Large numbers > > > To: Programming forum <[email protected]> > > > > > > > Hi, what's the largest number J can compute? > > > > I'm looking to compute 28433 * 2^7830457 + 1, which has > > 2357207 > > > > digits. I started calculating it, but it's taking a very > > long > > > > time (obviously), an I'm wondering how long it's likely to > > take, > > > > and whether it's even possible. > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
