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
