From: horndude77@...
Date: 2005-11-07T07:42:11+09:00
Subject: Re: Fun with Permutations

Sorry if this doesn't totally apply to this thread, but I felt like
playing with the factorial function for a bit. After taking a look at
the german thread I decided to see if I could speed it up also. Here's
what I came up with:

class Integer
    def fact1
        (1..self).inject { |n, fact| fact * n }
    end
    def fact2
        fact = 1
        (2..self).each { |n| fact *= n }
        fact
    end
    def fact3
        fact = 1
        i = 1
        while i <= self
            fact *= i
            i += 1
        end
        fact
    end
    def fact4
        fact = 1
        2.upto(self) { |n| fact *= n }
        fact
    end
    def fact5
        return 0 if self < 1
        return 1 if self < 2

        prod = 1
        n = self
        step = 10
        mul = 2
        if(self%2 == 1) then
            prod = self
            n -= 1
        end

        while(n>0)
            prod *= mul
            mul += step
            step += 8
            n -= 2
        end
        prod
    end
    def fact6
        return 0 if self<0
        return 1 if self<2
        return 2 if self==2
        endnum = self
        fact = 1
        if self % 3 == 1 then
            fact = self
            endnum = self - 1
        elsif self % 3 == 2 then
            fact = self*(self-1)
            endnum = self - 2
        end
        n = 1
        while n<self
            fact *= n*(n+1)*(n+2)
            n += 3
        end
        fact
    end
    def fact7
        return 1 if self < 2

        p = 1
        r = 1
        @_n = 1

        log2n = (Math.log(self)/Math.log(2)).floor
        h = 0
        shift = 0
        high = 1
        len = 0

        while(h != self)
            shift += h;
            h = self >> log2n;
            log2n -= 1
            len = high
            high = (h & 1) == 1 ? h : h - 1
            len = (high - len) / 2

            if(len > 0) then
                p *= product(len)
                r *= p
            end
        end
        return r << shift;
    end
    def product(n)
        m = n/2
        if(m == 0) then
            @_n += 2
            return @_n
        end
        if(n == 2)
            @_n += 4
            return @_n*(@_n-2)
        end
        product(n-m)*product(m)
    end
end

require 'benchmark'

def TESTBIG(meth)
    3.times { (10..600).each { |i| i.send meth } }
end

def TEST(meth)
    1000.times do
        for i in 0..12
            i.send meth
        end
    end
end

Benchmark.bm(20) do |bm|
    (1..7).each do |n|
        bm.report("fact#{n}:") { TEST("fact#{n}") }
    end
end

Benchmark.bm(20) do |bm|
    (1..7).each do |n|
        bm.report("fact#{n}:") { TESTBIG("fact#{n}") }
    end
end


I added the last three functions.

'fact5' uses this pattern to optimize the algorithm:
1*2 = 2
3*4 = 12 - 2 = 10
5*6 = 30 - 12 = 18 - 10 = 8
7*8 = 56 - 30 = 26 - 18 = 8
9*10 = 90 - 56 = 34 - 26 = 8
11*12 = 132 - 90 = 42 - 34 = 8
So it replaces a multiplication with a few additions. (not enough space
to fully explain it here)

'fact6' just unrolls the loop a bit.

'fact7' I got from
http://www.luschny.de/math/factorial/FastFactorialFunctions.htm and I
have no idea how it really works since there is no explaination on the
page. I just converted the code to ruby. I haven't sat down yet to
figure out how it works.

Here are my results:
                          user     system      total        real
fact1:                0.260000   0.040000   0.300000 (  0.318653)
fact2:                0.160000   0.030000   0.190000 (  0.187645)
fact3:                0.090000   0.010000   0.100000 (  0.106474)
fact4:                0.120000   0.030000   0.150000 (  0.154318)
fact5:                0.090000   0.010000   0.100000 (  0.108911)
fact6:                0.110000   0.000000   0.110000 (  0.116655)
fact7:                0.250000   0.020000   0.270000 (  0.283975)
                          user     system      total        real
fact1:                3.540000   0.420000   3.960000 (  3.964279)
fact2:                2.180000   0.210000   2.390000 (  2.399197)
fact3:                1.960000   0.000000   1.960000 (  1.968284)
fact4:                2.190000   0.190000   2.380000 (  2.383942)
fact5:                1.120000   0.000000   1.120000 (  1.133676)
fact6:                0.820000   0.000000   0.820000 (  0.821641)
fact7:                1.050000   0.080000   1.130000 (  1.129524)

It is somewhat annoying that unrolling the loop works that well for
larger numbers, but whatever works I guess. The other two also seem to
work fairly well.

The next thing to try would be the other fast algorithms from that fast
factorial page.

Ok, well hopefully this will be interesting to some.

-----Horndude77