Earlier quoted context omitted.
Lets see, what about factorial in constant memory? Exponentiation (a to the power of b, where they are positive integers) in logarithmic time (not using built-in exponentiation functions/syntax)? Anonymously add a constant to a number and return it (in a way that can be passed to a function like 'map' or some such)? def Factorial(x): output = 1 for i in xrange(x): output *= (i + 1) return output def Factorial2(x): re…
Thanks for that. First one (not 100% sure it's constant memory, I think perl optimises the for to avoid instantiating the (1..$n) list: #!/usr/bin/perl use Modern::Perl; use bigint; say fact(5000); sub fact { my ($n) = @_; my $output = 1; for my $i (1..$n) { $output *= $i; } return $output; } (Took the value up to 5000 to get something which ran long enough to get a measurement, on my laptop it runs (including startu…
It does since 5.005 - so for a good long time now :-)
The reduce version (again, I'm unsure of const mem req). Comes in at ~1.4s:
This would allocate the array I'm afraid. You'd could use something liek List::Gen's reduce() to get around that.