[Jprogramming] Large numbers

[henryhrich at nc.rr.com]

I see, thanks.  I'm not in a place where I can run those timings myself.

So the power will be several dozen times 800 seconds, which is what
the user was running into.

Henry Rich

---- Roger Hui <rhui000 at shaw.ca> 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: henryhrich at nc.rr.com
> Date: Wednesday, July 6, 2011 10:18
> Subject: Re: [Jprogramming] Large numbers
> To: Programming forum <programming at jsoftware.com>
> Cc: Roger Hui <rhui000 at shaw.ca>
> 
> > 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 <rhui000 at shaw.ca> 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 <purpleblues13 at googlemail.com>
> > > Date: Wednesday, July 6, 2011 8:32
> > > Subject: [Jprogramming] Large numbers
> > > To: Programming forum <programming at jsoftware.com>
> > > 
> > > > 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