rename math into maths, add function and specs

2 files changed, 199 insertions, 52 deletions

diff --git a/lib/ayk/math.rb b/lib/ayk/maths.rb
index 90a3b3a..5084eac 100644
--- a/lib/ayk/math.rb
+++ b/lib/ayk/maths.rb
@@ -1,14 +1,7 @@
 #! /usr/bin/env ruby
 # -*- coding: UTF-8 -*-
-
-#----------------------------------------------------------------------------
-#
-# File     : math.rb
-# Author   : Jérémy Zurcher <jeremy@asynk.ch>
-# Date     : 14/09/09 
-# License  :
 #
-#   Copyright (c) 2009 Jérémy Zurcher
+#   Copyright (c) 2009-2011 Jérémy Zurcher
 #
 #   Permission is hereby granted, free of charge, to any person obtaining
 #   a copy of this software and associated documentation files (the
@@ -34,9 +27,41 @@
 #def prime?
 #    ('1'*self) !~ /^1?$|^(11+?)\1+$/
 #end
-#def Math.gcd(x,y)
-#    /^(1+)\1*=\1+$/.match('1'*x+'='+'1'*y)[1].length
-#end
+#
+# return true if is a prime number
+def Math.prime? x
+    return true if x==2 or x==3
+    return false if x<2 or ( x%2 == 0 ) or ( x%3 == 0 )
+    r = (x**0.5).floor
+    d = 5
+    while d<=r
+        return false if ( x%d == 0 ) or ( x%(d+2) == 0 )
+        d+=6
+    end
+    true
+end
+#
+# return a bits long prime number
+def Math.prime bits
+    bytes_n,bits_n = bits.divmod 8
+    bytes = []
+    begin
+        # n = ( (rand()*Time.now.to_f).to_i & 0xff) | 0x80 random char better than rand(255) + 1 ?????
+        # rand currently uses a modified Mersenne Twister with a period of 2**19937-1
+        srand()
+        bytes.clear
+        bytes_n.times do
+            bytes << rand(255)+1
+        end
+        bytes << ( ((rand()*Time.now.to_f).to_i & 0xFF | 0x80) >> (8 - bits_n) )
+        n = Bignum.from_bytes bytes.inject(''){|s,b|s+=b.chr}
+        n+= 1 if n%2 == 0
+        while not Math::prime? n
+            n += 2
+        end
+    end while n.bits != bits
+    n
+end
 #
 # generate prime numbers < n
 def Math.sieve n
@@ -50,62 +75,110 @@ def Math.sieve n
     sieve.compact
 end
 #
+#def Math.gcd(x,y)
+#    /^(1+)\1*=\1+$/.match('1'*x+'='+'1'*y)[1].length
+#end
+#
 # return greater common divisor
 def Math.gcd x, y
     y,x=x,y if x<y
-    while y > 0 
-        r = x % y 
+    while y > 0
+        r = x % y
         x = y
         y = r
     end
     return x
 end
 #
-# return true if is a prime number
-def Math.prime? x
-#    return false if x <0
-    if x==3
-        return true
-    elsif x % 2 == 0
-        return false
-    elsif x % 3 == 0
-        return false
+def Math.prime_power_modulus(b, p, m)
+    if p == 1
+        b % m
+    elsif (p & 0x1) == 0
+        t = prime_power_modulus(b, p >> 1, m)
+        (t * t) % m
     else
-        r = (x**0.5).floor
-        d = 5
-        while d<r
-            if x % d == 0
-                return false
-            end
-            if x % (d + 2) == 0
-                return false
-            end
-            d+=6
+        (b * prime_power_modulus(b, p-1, m)) % m
+    end
+end
+#
+class Fixnum
+    #
+    class << self
+        def from_bytes bytes
+            val = 0
+            idx = 0
+            bytes.each_byte{ |b|
+                val += b << 8 * idx
+                idx += 1
+            }
+            val
+        end
+    end
+    #
+    def to_bytes
+        str = ''
+        int = self
+        while int!=0 do
+            int,r = int.divmod 256
+            str += r.chr
         end
-        return true
+        str
     end
+    #
+    def bits
+        s = self.to_bytes
+        while s[-1].ord==0
+            s.slice!(-1)
+        end
+        bit_len = s.length * 8
+        tmp = s[-1].ord
+        while not tmp & 0x80
+            bit_len-=1
+            tmp <<=1
+        end
+        bit_len
+    end
+    #
 end
 #
-# return a bits long prime number
-def Math.prime bits
-    bytes_n,bits_n = bits.divmod 8
-    bytes = []
-    begin
-        # n = ( (rand()*Time.now.to_f).to_i & 0xff) | 0x80 random char better than rand(255) + 1 ?????
-        # rand currently uses a modified Mersenne Twister with a period of 2**19937-1
-        srand()
-        bytes.clear
-        bytes_n.times do
-            bytes << rand(255)+1
+class Bignum
+    #
+    class << self
+        def from_bytes bytes
+            val = 0
+            idx = 0
+            bytes.each_byte{ |b|
+                val += b << 8 * idx
+                idx += 1
+            }
+            val
         end
-        bytes << ( ((rand()*Time.now.to_f).to_i & 0xFF | 0x80) >> (8 - bits_n) )
-        n = Bignum.from_bytes( bytes.inject(''){|s,b|s+=b.chr} )
-        puts n
-        n+= 1 if n%2 == 0
-        while not Math::prime? n
-            n += 2
+    end
+    #
+    def to_bytes
+        str = ''
+        bint = self
+        while bint!=0 do
+            bint,r = bint.divmod 256
+            str += r.chr
         end
-    end while n.bits != bits
-    n
+        str
+    end
+    #
+    def bits
+        s = self.to_bytes
+        while s[-1].ord==0
+            s.slice!(-1)
+        end
+        bit_len = s.length * 8
+        tmp = s[-1].ord
+        while not tmp & 0x80
+            bit_len-=1
+            tmp <<=1
+        end
+        bit_len
+    end
+    #
 end
 #
+#EOF
diff --git a/spec/maths_spec.rb b/spec/maths_spec.rb
new file mode 100644
index 0000000..aaa76e6
--- /dev/null
+++ b/spec/maths_spec.rb
@@ -0,0 +1,74 @@
+#! /usr/bin/env ruby
+# -*- coding: UTF-8 -*-
+#
+require 'ayk/maths'
+#
+describe "Maths" do
+    #
+    PRIMES = [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
+        101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199,
+        211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293,
+        307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397,
+        401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499,
+        503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599,
+        601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691,
+        701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797,
+        809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887,
+        907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997
+    ]
+    describe Math do
+        it "check Math.prime? on 1..1000" do
+            (0..1000).each do |n|
+                if PRIMES.include? n
+                    Math.prime?(n).should be_true
+                else
+                    Math.prime?(n).should be_false
+                end
+            end
+        end
+        it "check Math.prime" do
+            Math.prime?( Math.prime 8).should be_true
+        end
+        it "check Math.sieve on 1..1000" do
+            primes = Math.sieve 1000
+            primes.length.should eql PRIMES.length
+            primes.each do |p|
+                PRIMES.include?(p).should be_true
+            end
+        end
+        it "check Math.gcd" do
+            Math.gcd(123,27).should eql 3
+            Math.gcd(54,24).should eql 6
+        end
+    end
+    describe Fixnum do
+        it '#to_bytes #from_bytes should work' do
+            16777700.should eql Bignum.from_bytes(16777700.to_bytes)
+        end
+        it '#bits' do
+            (1..255).each do |n| n.bits.should eql 8 end
+            (256..500).each do |n| n.bits.should eql 16 end
+            (60000..60500).each do |n| n.bits.should eql 16 end
+            (65536..66000).each do |n| n.bits.should eql 24 end
+            (16777000..16777215).each do |n| n.bits.should eql 24 end
+            (16777216..16777700).each do |n| n.bits.should eql 32 end
+            (1073741000..1073741823).each do |n| n.bits.should eql 32 end
+            (1073741000..1073741823).each do |n| n.should be_a Fixnum end
+        end
+    end
+    describe Bignum do
+        it '#to_bytes #from_bytes should work' do
+            0x217962755220666f207463657073612074656577732061207369206d756e676942
+            .should eql Bignum.from_bytes(0x217962755220666f207463657073612074656577732061207369206d756e676942.to_bytes)
+        end
+        it '#bits' do
+            (1073741824..1073742000).each do |n| n.should be_a Bignum end
+            (1073741824..1073742000).each do |n| n.bits.should eql 32 end
+            (4294967000..4294967295).each do |n| n.bits.should eql 32 end
+            (4294967296..4294967500).each do |n| n.bits.should eql 40 end
+        end
+    end
+    #
+end
+#
+#EOF