CODEWITHSUNDEEP
rubyfor-loopintegermax
Kai Durai
Kai Durai

Reputation: 431

Maximum Calculation Possible

I have a method to calculate the factorial of an input number

def fact( n )
  if (n == 0)
    1
  else
    n * fact(n-1)
  end
end

I want to create a loop that will test what the maximum possible calculable value is for this method. For my machine this number is 8734, but I found that through trial and error.

My idea is to create a for/ each loop and test whether the returned result is a real number or not. I only want to puts the last numerical value that actually produces a real numerical result.

Thanks!

Upvotes: 1

Views: 61

Answers (2)

Cary Swoveland
Cary Swoveland

Reputation: 110725

You can do as @spickermann suggests, but there is no need to search for the argument for fact at which the exception is raised. Rather, just compute fact(n) for any suitably large value of n (e.g. n = 100_000), increment a stack depth counter each time fact is called, and report the value of that counter when the SystemStackError exception is raised. The following code performs that calculation for various values of n, showing that the value of n is not important, so long as it is suitably large. I would think n = 100_000 would be plenty large for any Ruby implementation, but make it a million if you like.

def fact( n )
  @stack_size += 1
  if (n == 0)
    1
  else
    n * fact(n-1)
  end
end

[10_000, 20_000, 50_000, 100_000, 8733, 8732].each do |n|
  print "n=#{n.to_s.ljust(6)}: "
  begin
    @stack_size = 0
    fact(n)
  rescue SystemStackError
    puts "stack level too deep at: #{@stack_size}"
  end
end

# n=10000 : stack level too deep at: 8733
# n=20000 : stack level too deep at: 8733
# n=50000 : stack level too deep at: 8733
# n=100000: stack level too deep at: 8733
# n=8733  : stack level too deep at: 8733
# n=8732  :

Note that the exception was not raised when n => 8732.

Does the maximum stack depth depend on the method? Most certainly! If we replace fact with:

def fact(n)
  @stack_size += 1
  fact(n-1)
end

we get:

# stack level too deep at: 9356

Upvotes: 0

spickermann
spickermann

Reputation: 106972

I would do something like this:

i = 1
loop do
  begin
    fact(i)
  rescue SystemStackError
    puts "stack level too deep at: #{i}"
    break
  end

  i += 1
end

Note that this is a very naive algorith that checks every number and might take some time. It would be must faster to Do some kind of binary search on a range of numbers.

Upvotes: 1

Related Questions