monochrom 2017-03-08 19:57:48
If you use GHC, you want to multiply two numbers of similar magnitude. You want to multiply two large numbers ASAP, not postpone it by multiplying a large number by a small number.
monochrom 2017-03-08 19:58:45
This is because GHC is going to call GMP for multiplication, and reaching the multiplication of two large numbers earlier means GMP uses the advanced multipliers earlier.
monochrom 2017-03-08 19:59:30
(Ideally you would rather call GMP's factorial function directly, which uses an even more advanced algorithm. But GHC doesn't expose this.)
pacak 2017-03-08 20:01:41
Let's assume every number in factorial is the same. If you split a huge list in half and take product of every half you'll get two numbers with N digits each - that would be one expensive multiplication and product will give 2N. Split every of those lists in half - there will be only N/2 digits and so on.
SexHendrix 2017-03-08 20:01:55
whenever i have to write a load of horrible functions to get from input to the datatype i want, i make a function called `magic` that is just all of them composed
pacak 2017-03-08 20:02:08
If you multiply them as a tree you'll get one multiplication of size N, 2 of size N/2, 4 of size N/4 and so on
SexHendrix 2017-03-08 20:02:28
then just `magic input`
pacak 2017-03-08 20:02:29
It's much cheaper than multiplying big number by small number N times
SexHendrix 2017-03-08 20:03:42
https://ptpb.pw/DKsV :]
