From 91d70d775dd11a9ec350ca7f3b6d403fa897aadc Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?J=C3=A9r=C3=A9my=20Zurcher?= Date: Fri, 5 Aug 2011 23:38:11 +0200 Subject: rename math into maths, add function and specs --- lib/ayk/math.rb | 111 -------------------------------- lib/ayk/maths.rb | 184 +++++++++++++++++++++++++++++++++++++++++++++++++++++ spec/maths_spec.rb | 74 +++++++++++++++++++++ 3 files changed, 258 insertions(+), 111 deletions(-) delete mode 100644 lib/ayk/math.rb create mode 100644 lib/ayk/maths.rb create mode 100644 spec/maths_spec.rb diff --git a/lib/ayk/math.rb b/lib/ayk/math.rb deleted file mode 100644 index 90a3b3a..0000000 --- a/lib/ayk/math.rb +++ /dev/null @@ -1,111 +0,0 @@ -#! /usr/bin/env ruby -# -*- coding: UTF-8 -*- - -#---------------------------------------------------------------------------- -# -# File : math.rb -# Author : Jérémy Zurcher -# Date : 14/09/09 -# License : -# -# Copyright (c) 2009 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 -# "Software"), to deal in the Software without restriction, including -# without limitation the rights to use, copy, modify, merge, publish, -# distribute, sublicense, and/or sell copies of the Software, and to -# permit persons to whom the Software is furnished to do so, subject to -# the following conditions: -# -# The above copyright notice and this permission notice shall be -# included in all copies or substantial portions of the Software. -# -# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, -# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF -# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND -# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE -# LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION -# OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION -# WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. -# -#---------------------------------------------------------------------------- -# -#def prime? -# ('1'*self) !~ /^1?$|^(11+?)\1+$/ -#end -#def Math.gcd(x,y) -# /^(1+)\1*=\1+$/.match('1'*x+'='+'1'*y)[1].length -#end -# -# generate prime numbers < n -def Math.sieve n - sieve = [nil, nil] + (2 .. n).to_a - (2 .. Math.sqrt(n)).each do |i| - next unless sieve[i] - (i*i).step(n, i) do |j| - sieve[j] = nil - end - end - sieve.compact -end -# -# return greater common divisor -def Math.gcd x, y - y,x=x,y if x 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 - else - r = (x**0.5).floor - d = 5 - while d> (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 - end while n.bits != bits - n -end -# diff --git a/lib/ayk/maths.rb b/lib/ayk/maths.rb new file mode 100644 index 0000000..5084eac --- /dev/null +++ b/lib/ayk/maths.rb @@ -0,0 +1,184 @@ +#! /usr/bin/env ruby +# -*- coding: UTF-8 -*- +# +# 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 +# "Software"), to deal in the Software without restriction, including +# without limitation the rights to use, copy, modify, merge, publish, +# distribute, sublicense, and/or sell copies of the Software, and to +# permit persons to whom the Software is furnished to do so, subject to +# the following conditions: +# +# The above copyright notice and this permission notice shall be +# included in all copies or substantial portions of the Software. +# +# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF +# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE +# LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION +# OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION +# WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. +# +#---------------------------------------------------------------------------- +# +#def prime? +# ('1'*self) !~ /^1?$|^(11+?)\1+$/ +#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 + sieve = [nil, nil] + (2 .. n).to_a + (2 .. Math.sqrt(n)).each do |i| + next unless sieve[i] + (i*i).step(n, i) do |j| + sieve[j] = nil + end + end + 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 0 + r = x % y + x = y + y = r + end + return x +end +# +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 + (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 + 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 +# +class Bignum + # + 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 = '' + bint = self + while bint!=0 do + bint,r = bint.divmod 256 + str += r.chr + end + 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 -- cgit v1.1-2-g2b99