Never been to DZone Snippets before?

Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

About this user

« Newer Snippets
Older Snippets »
Showing 11-20 of 49 total

Random numbers in Ruby


# Pseudo random number generator
# From: http://gnuvince.wordpress.com/2005/11/24/pseudo-random-number-generator
# Author: Vincent Foley-Bourgon

def random_number
  t = Time.now.to_f / (Time.now.to_f % Time.now.to_i)
  random_seed = t * 1103515245 + 12345;
  (random_seed / 65536) % 32768;
end

10.times { puts random_number }

cnt = Array.new(10,0)
20000.times { cnt[(random_number % 10).to_i] += 1 }
p cnt
puts


# Ruby Gaussian Random Number Generator
# Author: Glenn
# http://webhost101.net/rails/typo/articles/2007/07/31/ruby-gaussian-random-number-generator

def gaussian_rand 
   u1 = u2 = w = g1 = g2 = 0  # declare
   begin
     u1 = 2 * rand - 1
     u2 = 2 * rand - 1
     w = u1 * u1 + u2 * u2
   end while w >= 1
   
   w = Math::sqrt( ( -2 * Math::log(w)) / w )
   g2 = u1 * w;
   g1 = u2 * w;
   # g1 is returned  
end

sum = 0
sumsq = 0
n = 1000
0.upto(n) do 
  #r = gaussian_rand
  r = gaussian_rand * 100 + 50   # new_random_number = gaussian_rand * standard_deviation + average
  #puts r
  sum += r
  sumsq += (r*r)
end

ave = sum/n
stddev = Math::sqrt(sumsq/n - ave * ave)
puts "Average = #{ave}"
puts "StdDev = #{stddev}"
puts


# Random Number Generator
# http://scutigena.sourceforge.net/test-random.html
# http://scutigena.sourceforge.net/sources/ruby-1.7.2/random.html
# $Id: random.ruby,v 1.2 2003/12/30 01:25:05 davidw Exp $

IM = 139968
IA = 3877
IC = 29573

$last = 42.0
def gen_random (max) (max * ($last = ($last * IA + IC) % IM)) / IM end

10.times do
    puts gen_random(100000.0)
end

printf "%.5f\n", gen_random(100.0)
puts


# From: http://matt.blogs.it/entries/00002641.html
# Author: Matt Mower
# cf. http://www.taygeta.com/random/gaussian.html
# cf. http://www.bearcave.com/misl/misl_tech/wavelets/hurst/random.html

def box_mueller( mean = 0.0, stddev = 1.0 )
  x1 = 0.0, x2 = 0.0, w = 0.0

  until w > 0.0 && w < 1.0
    x1 = 2.0 * rand - 1.0
    x2 = 2.0 * rand - 1.0
    w = ( x1 * x2 ) + ( x2 * x2 )
  end

  w = Math.sqrt( -2.0 * Math.log( w ) / w )
  r = x1 * w

  mean + r * stddev
end

10.times { puts box_mueller(5.0, 1.0) }
puts


# Generating random numbers with a specified distribution
# From: http://www.cs.nyu.edu/~michaels/blog/?p=24
# Author: Michael Schidlowsky

def gen
  (x=rand)>0.5 ? x : (x < rand/2.0) ? 1.0 - x : x
end

def gen2
   (x = rand) && rand ? 1.0 - x : x
end

def compute_distribution(numSamples, &block)
   samples = []
   values = 10
   numSamples.times{samples << yield}
   dist = Array.new(values, 0)
   samples.each{ |s| dist[(s*values).floor] += 1 }
   dist
end

p compute_distribution(1000){rand}
p compute_distribution(1000){gen}
p compute_distribution(1000) { gen2 }
puts


# Random number generation for a triangular distribution
# From: http://www.brighton-webs.co.uk/distributions/triangular.asp
# cf. http://en.wikipedia.org/wiki/Triangular_distribution

def rng(m, low, high)

   # cf. the parameter info at http://www.brighton-webs.co.uk/distributions/triangular.asp
   return nil unless high > low && m > low && m < high    

   u = rand

   if u <= (m-low)/(high-low)
      r = low+ Math.sqrt(u*(high-low)*(m-low))
   else
      r = high - Math.sqrt((1.0-u)*(high-low)*(high-m))
   end

end

10.times do
  #puts rng(0.0, -25.0, 25.0)
  puts rng(50.0, 25.0, 75.0)
end
puts


# From: http://www.ruby-forum.com/topic/95931
# Author: Christoffer Lernö

class Range
  def rand
    return first if exclude_end? && last == first
    Kernel::rand(last - first + (exclude_end? ? 0 : 1)) + first
  end
end

r1 = -9..9
r2 = -90...100
p r1.rand, r2.rand

r3 = 0..9

num = []
10.times do
   num << r3.rand
   if num.first.zero? then num.shift; redo end
end

p num
puts num.to_s.to_i
puts


# See:
# http://redcorundum.blogspot.com/2008/01/randomizing-array-revisited.html
# http://redcorundum.blogspot.com/2006/12/randomizing-array-and-other-faqs.html
# http://szeryf.wordpress.com/2007/06/19/a-simple-shuffle-that-proved-not-so-simple-after-all/

class Array
  def shuffle
    array = dup
    size.downto 2 do |j|
      r = rand j
      array[j-1], array[r] = array[r], array[j-1]
    end
    array
  end
end

array = (1..50).to_a

10.times { p array.shuffle.first(10) }


#-------------------


class RNG

   def num(min=8,max=min+5,iter=1)

      return nil unless min.is_a?(Integer) && max.is_a?(Integer) && max > min && iter.is_a?(Integer)

      ret = []
      stats = Hash.new(0)     # optional; cf. stats[random_num] += 1
      digits = Array(0..9).sort_by {rand}
      #digits = (Array(0..9) * (rand(4)+1)).sort_by {rand}
      digits_size = digits.size

      iter.times do
         count = 0
         len = min + rand(max-min+1)
         ar = []
         while count < len
            i = rand(digits_size)    # get a random array index
            random_num = digits.at(i)
            stats[random_num] += 1
            ar << random_num
            digits = digits.sort_by {rand}
            count += 1
            if count == 1 && ar.first.zero? then ar.shift; stats[0] -= 1; count = 0 end
         end
         ret << ar.to_s.to_i
      end  # iter
      #ret
      ret << stats   # optional
   end

end

puts

min = 8
max = 13
iter = 10000
result =  RNG.new.num(min, max, iter)
stats = result.pop

t = 0
stats.each_value { |v| t += v }  # get the overall frequency

n = 0
t = t * 1.0
m = t / 10.0 

stats.sort.each do |k,v| 
   i = (v / t) * 100.0
   x = v > m ? v - m : m - v
   y = (x / m) * 100.0
   n += i
   puts "#{k}  ::  #{"%.2f" % m}  ::  #{v}  ::  #{"%.2f" % i} %  ::  #{ "%.2f" % ((m-v) * -1) }  ::  #{"%.2f" % y} %"
end

puts n, m, t

puts
puts RNG.new.num(20, 25, 10)[0..-2]

puts
rn = RNG.new.num(80, 100)
puts rn[0..-2]
p rn.last


Lottery


Author: ntk
License: The MIT License, Copyright (c) 2007 ntk
Inspired by: Lottery Quick Pick
Hints: Lottery mathematics


class Lottery

   def playing(i=1, n1=0, r1=0..0, n2=0, r2=0..0)

      return nil unless i.is_a?(Integer) && n1.is_a?(Integer) && n1 > 0 && r1.is_a?(Range) && n2.is_a?(Integer) && r2.is_a?(Range)
      stats = Hash.new(0)   # optional; stores the frequency of picked numbers, cf. stats[random_num] += 1
      ret = []

      random_procs = [ 
         lambda { |a,n| a.slice!(rand(n)) },      # a is an array, n an integer
         lambda { |a,n| a.slice!(rand(n) * -1) }, 
         lambda { |a,n| a.slice!((rand(n) * -1) + rand(n)) },
         lambda { |a,n| a.slice!((rand(n) - rand(n))) }, 
         lambda { |a,n| a.reverse!.slice!(rand(n)) },
         lambda { |a,n| a.reverse!.slice!(rand(n) * -1) }, 
         lambda { |a,n| a.reverse!.slice!((rand(n) * -1) + rand(n)) },
         lambda { |a,n| a.reverse!.slice!((rand(n) - rand(n))) } 
      ] 

      i.times do
         numbers = r1.to_a.sort_by {rand}
         num = numbers.size
         ar = []
         count = 0

         while count < n1 + n2

            count += 1

            if count > n1 && n2 > 0
               numbers2 = r2.to_a
               numbers2 = (numbers & numbers2).sort_by {rand} 
               num2 = numbers2.size
               count2 = 0
               while count2 < n2
                  count2 += 1
                  i = rand(random_procs.size)   # get a random array index for random_procs array
                  random_procs = random_procs.sort_by {rand}      
                  random_num = random_procs.at(i).call(numbers2, num2)
                  stats[random_num] += 1
                  ar << random_num
                  numbers2 = numbers2.sort_by {rand}
                  num2 -= 1
               end   # while

               if count2 > 1 then count += (count2-1) end  
               #break   # alternative
              
            else

               i = rand(random_procs.size)                               
               random_procs = random_procs.sort_by {rand}  
  
               random_num = random_procs.at(i).call(numbers, num)
               stats[random_num] += 1
               ar << random_num

=begin
              if rand(num) % (rand(num) + 1) == rand(num)               #  alternative
                  random_num = random_procs.at(i).call(numbers, num)
                  stats[random_num] += 1
                  ar << random_num
               else
                  random_num = numbers.slice!(rand(num))
                  stats[random_num] += 1
                  ar << random_num
               end
=end

               numbers = numbers.sort_by {rand}
               num -= 1

            end          # if
         end             # while
         ret << ar
      end
      #ret
      ret << stats   # optional
   end

end


puts
puts "UK National Lottery, German Lotto 6/49, ..."

ndraws = 10
result = Lottery.new.playing(ndraws, 6, 1..49)
stats = result.pop

result.each do |t| 
   puts t.sort.join('-')
end

puts
n = 0
stats.sort.each do |k,v| 
   i = (v / (ndraws * 6.0) ) * 100.0
   n += i
   puts "#{k} :: #{v} :: #{i}%"
end
p n

puts
puts "US Powerball Lottery"
Lottery.new.playing(ndraws, 5, 1..55, 1, 1..42)[0..-2].each do |t| 
   n = t.pop
   puts "#{t.sort.join('-')}  and  #{n}"
end

puts
puts "Mega Millions"
Lottery.new.playing(ndraws, 5, 1..56, 1, 1..46)[0..-2].each do |t| 
   n = t.pop
   puts "#{t.sort.join('-')}  and  #{n}"
end

puts
puts "EuroMillions"
Lottery.new.playing(ndraws, 5, 1..50, 2, 1..9)[0..-2].each do |t| 
   n1 = t.pop
   n2 = t.pop
   puts "#{t.sort.join('-')}  and  #{n1}-#{n2}"
end


puts
puts "US Powerball Lottery"

ndraws = 10
nums = [5, 23, 25, 33, 34]
pb = 31

matches = []
n = 0

Lottery.new.playing(ndraws, 5, 1..55, 1, 1..42)[0..-2].each do |t| 
   i = t.pop
   t = t.sort
   if (t & nums).size > matches.size || ( matches.size == 0 && i == pb )
      matches = t & nums 
      i == pb ? n = i : n = 0
   end
end

if pb == n && !matches.empty?
   puts "Your numbers: #{nums.join('-')} and #{pb}\nYour matches: #{matches.join('-')} and #{n}"
elsif pb == n && matches.empty?
   puts "Your numbers: #{nums.join('-')} and #{pb}\nYour matches: [] and #{n}"
else
   puts "Your numbers: #{nums.join('-')} and #{pb}\nYour matches: #{matches.join('-')}"
end


Miller-Rabin prime test in Ruby


# From: http://en.wikipedia.org/wiki/Miller-Rabin_primality_test

class Integer
   def prime?
     n = self.abs()
     return true if n == 2
     return false if n == 1 || n & 1 == 0

     # cf. http://betterexplained.com/articles/another-look-at-prime-numbers/ and
     # http://everything2.com/index.pl?node_id=1176369

     return false if n > 3 && n % 6 != 1 && n % 6 != 5     # added

     d = n-1
     d >>= 1 while d & 1 == 0
     20.times do                               # 20 = k from above
       a = rand(n-2) + 1
       t = d
       y = ModMath.pow(a,t,n)                  # implemented below
       while t != n-1 && y != 1 && y != n-1
         y = (y * y) % n
         t <<= 1
       end
       return false if y != n-1 && t & 1 == 0
     end
     return true
   end
end
 
module ModMath
   def ModMath.pow(base, power, mod)
     result = 1
     while power > 0
       result = (result * base) % mod if power & 1 == 1
       base = (base * base) % mod
       power >>= 1;
     end
     result
   end
end


#------------------------------------------------------------------


# From: http://www.h2np.net/tips/ruby-cipher-math.txt
# Author: Hironobu SUZUKI

# $Id: mathh.rb,v 1.5 2002/11/24 16:15:56 hironobu Exp $
# Simple Secure Stream Cryptography
# Mathematical Library
# Hironobu SUZUKI <hironobu@h2np.net>
# LGPL, (C) 2002, Hironobu SUZUKI

class Random  
  def initialize()
    @random_device="/dev/urandom"
    @verbose=false
  end
  def random_device=(str)
    @random_device=str
  end
  def verbose
    @verbose=true
  end
  def get(size)
    if (@verbose) ;STDERR.print "+";end
    value=0
    r=File.open(@random_device)
    r.read(size).each_byte {|c|
      value = (value << 8) + c.to_i
    }
    r.close
    return value
    
  end
  def get_prime(lower,higher)
    bytesize = higher.bytesize
    while true
      r = self.get(bytesize)
      if (r % 2 == 0) ; r -= 1 ;   end
      if ( lower <=  r && r <= higher && r.prime? == true )
	return r
      end
    end
  end
end


class Integer
  def cdiv(d)			# ceil divide
    w=self.divmod(d)
    if w[1] > 0 ;  w[0] +=1 ; end
    return w[0]
  end
  def powm(i,n)	# square-and-multiply for exp modulo n
    if ( i == 0 )
      return 1
    end
    b=1
    a=self

    if ( (i & 1) == 1 )
      b=a
    end
    i = i>>1

    while ( i > 0 )
      a = (a * a) % n
      if ( (i & 1) == 1 )
	b = (a * b) % n 
      end
      i = i>>1
    end
    return b
  end
  def gcd(b)			# GCD
    a = self
    if ( a < b ); t=b; b=a; a=t; end
    while b > 0 
      r = a % b 
      a = b
      b = r
    end
    return a
  end
  def invert(n)  # Extension Euclid Algorithm
    a = n        # See Knuth's The Art of Computer Programming 
    b = self % n # Vol2 pp.342 -- 343  
    p = 0 ; q = 1;  v = 0;  u = 1;
    while q > 0 
      p = a / b
      q =  a % b
      w = v - (p*u)
      ## DEBUG    printf "%d = %d(%d) + %d  (%d)\n", a,p,b,q,v ###
      a = b
      b = q
      v = u
      u = w
    end
    return (v+n) % n
  end

# Miller-Rabin Test  (Prime Test)
# See, http://www.cs.albany.edu/~berg/csi445/Assignments/pa4.html
  def bitarray(n) 
    b=Array::new  
    i=0       
    v=n
    while v > 0
      b[i] = (0x1 & v)
      v = v/2
      i = i + 1
    end
    return b
  end
  def miller_rabin(n,s)
    b=bitarray(n-1)
    i=b.size 
    j =1
    while j <= s
      a = 1 + (rand(n-2).to_i)
      if witness(a,n,i,b) == true
	return false
      end
      j+=1
    end
    return true
  end
  def witness(a,n,i,b)
    d=1
    x=0
    while i > 0 
      x = d 
      d = (d**2) % n
      if ( (d == 1) && (x != 1) && (x != (n-1)) )
	return true
      end
      if ( b[i-1] == 1 )
	d = (d * a ) % n
      end
      i -= 1
    end
    if ( d != 1) 
      return true
    end
    return false
  end

  #def prime?
  def is_prime?
    a = self
    return miller_rabin(a,30)    
  end

  def bytesize
    n = self
    i=0
    while n > 0
      n = n >> 8
      i += 1
    end
    return i
  end
  def bitsize
    n = self
    i=0
    while n > 0
      n = n >> 1
      i += 1
    end
    return i
  end
end


p 107565456790871.prime?      # true
p 107565456790871.is_prime?   # true

a = 107565456790871

begin
  a += 2
end while !a.prime? && !a.is_prime?

puts a   #=> 107565456790991 (next prime)


nsieve for Ruby


From: The Great Computer Language Shootout: nsieve-bits Ruby
Author: Glenn Parker


CharExponent = 3
BitsPerChar = 1 << CharExponent
LowMask = BitsPerChar - 1

def sieve(m)
  ret = []
  items = "\xFF" * ((m / BitsPerChar) + 1)
  masks = ""
  BitsPerChar.times do |b|
    masks << (1 << b).chr
  end

  count = 0
  pmax = m - 1
  2.step(pmax, 1) do |p|
    if items[p >> CharExponent][p & LowMask] == 1
      ret << p
      count += 1
      p.step(pmax, p) do |mult|
	a = mult >> CharExponent
	b = mult & LowMask
	items[a] -= masks[b] if items[a][b] != 0
        #p items
      end
    end
  end
  #count
  ret
end

n = (ARGV[0] || 2).to_i
n.step(n - 2, -1) do |exponent|
  break if exponent < 0
  m = 2 ** exponent * 10_000
  primes = sieve(m)
  count = primes.size
  puts
  printf "Primes up to %8d %8d\n", m, count
  puts "last ten primes: #{primes[-10..-1].join(' ')}"
  puts
end


Diffie-Hellman key exchange in Ruby

From: http://labs.musecurity.com/2007/05/09/diffie-hellman-in-ruby/
Author: kowsik


class Integer
    # Compute self ^ e mod m
    def mod_exp e, m
        result = 1
        b = self
        while e > 0
            result = (result * b) % m if e[0] == 1
            e = e >> 1
            b = (b * b) % m
        end
        return result
    end

    # A roundabout, slow but fun way of counting bits.
    def bits_set
        ("%b" % self).count('1')
        #to_s(2).count('1')   # alternative
        #count = 0         # alternative
        #byte = self.abs
        #count += byte & 1 and byte >>= 1 until byte == 0     # cf. http://snippets.dzone.com/posts/show/4233
        #count
    end
end


class DH
    attr_reader :p, :g, :q, :x, :e

    # p is the prime, g the generator and q order of the subgroup
    def initialize p, g, q
        @p = p
        @g = g
        @q = q
    end

    # generate the [secret] random value and the public key
    def generate tries=16
        tries.times do
            @x = rand(@q)
            @e = self.g.mod_exp(@x, self.p)
            return @e if self.valid?
        end
        raise ArgumentError, "can't generate valid e"
    end

    # validate a public key
    def valid? _e = self.e
        _e and _e.between?(2, self.p-2) and _e.bits_set > 1
    end

    # compute the shared secret, given the public key
    def secret f
        f.mod_exp(self.x, self.p)
    end
end

alice = DH.new(53, 5, 23)
bob   = DH.new(53, 5, 15)
alice.generate
bob.generate

alice_s = alice.secret(bob.e)
bob_s   = bob.secret(alice.e)
puts alice_s
puts bob_s


Punycoded URLs in Ruby

This is just a proof-of-concept snippet for how to internationalize domain names using punycode4r (sudo gem install punycode4r).

For more information please see:
- Punycode
- Internationalized domain name



#!/usr/local/bin/ruby -Ku

# NOTE: The following is not the complete source code by Kazuhiro NISHIYAMA.
#       For the full source code with more features, comments & test cases please see: 
#       open -e `gem environment gemdir`/gems/punycode4r-0.2.0/lib/punycode.rb
#
# This is pure Ruby implementing Punycode (RFC 3492).
# (original ANSI C code (C89) implementing Punycode is in RFC 3492)
#
# copyright (c) 2005 Kazuhiro NISHIYAMA
# You can redistribute it and/or modify it under the same terms as Ruby.


require "unicode"     # sudo gem install unicode

module Punycode

  module Status
    class Error < StandardError; end
    class PunycodeSuccess; end
    # Input is invalid.
    class PunycodeBadInput < Error; end
    # Output would exceed the space provided.
    class PunycodeBigOutput< Error; end
    # Input needs wider integers to process.
    class PunycodeOverflow < Error; end
  end
  include Status


  BASE = 36; TMIN = 1; TMAX = 26; SKEW = 38; DAMP = 700
  INITIAL_BIAS = 72; INITIAL_N = 0x80; DELIMITER = 0x2D

  module_function

  def basic(cp)
    cp < 0x80
  end

  def delim(cp)
    cp == DELIMITER
  end

  def decode_digit(cp)
    cp - 48 < 10 ? cp - 22 :  cp -