[ruby-talk:10219] Re: limits on computation?

Mike Wilson <[e-mail]> writes:

> Just fooling around some, I ran this
> 
> irb(main):001:0> 1020939**28329282

 ...

> So I'm curious why ruby seems to have no limit on the stupidity of
> the user ;).  Perl is known to hand the user a good
> (tree_branch_height - (user_height + 1)) worth of rope, but still
> recognizes that this is a fruitless pursuit.

Just as a matter of interest, I played with this a bit:


  base = 1020939
  n = 1
  number = base

  loop do
    printf "%6d: %6d %f\n", n, number.size, number.size.to_f/n
    n += 1
    number *= base
  end

I ran this and the size of the representation of 1020939^n seems to to
be pretty consistently 2.4955*n. So, I'm guessing that when
n=28329282, the number would be stored in roughly 70Mb, which isn't
exceptionally scary.

Then I played around with timings. As you'd expect, the
multiplications are greater than O(n^2). Here are some timings from my
box calculating 1020939^n for various n:
    n              time
    10,000          1.18
    20,000          4.72
    40,000         19.45
    80,000         80.12
   100,000        124.03
   200,000        582

I'm guessing that 1020939**28329282 would take something like
12,000,000 seconds to compute, roughly 140 days.

So, it seems like on a sensible-sized box, this is actually a viable
calculation for Ruby to perform (if you really, really want to know
the answer and don't mind waiting).

You just didn't wait long enough...  ;-)


Dave




Footnotes: 
ケ  I'm no mathematician, though, so I'm guessing here. This could be
way off as the numbers start to climb.