Module: LibTom::Math

Defined in:
lib/libtom/math.rb,
lib/libtom/math/prime.rb,
lib/libtom/math/bignum.rb,
lib/libtom/math/gemspec.rb,
lib/libtom/math/version.rb,
lib/libtom/math/specification.rb,
ext/libtom/lt_math.c

Overview

LibTom::Math

Interface to the LibTomMath free open source portable number theoretic multiple-precision integer library.

What does it do?

The library provides a vast array of highly optimized routines from various branches of number theory.

  • Simple Algebraic

    • Addition

    • Subtraction

    • Multiplication

    • Squaring

    • Division

  • Digit Manipulation

    • Shift left/right whole digits (mult by 2b by moving digits)

    • Fast multiplication/division by 2 and 2k for k>1

    • Binary AND, OR and XOR gates

  • Modular Reductions

    • Barrett Reduction (fast for any p)

    • Montgomery Reduction (faster for any odd p)

    • DR Reduction (faster for any restricted p see manual)

    • 2k Reduction (fast reduction modulo 2p - k for k < MP_MASK and for k > MP_MASK)

    • The exptmod logic can use any of the five reduction algorithms when appropriate with a single function call.

  • Number Theoretic

    • Greatest Common Divisor

    • Least Common Multiple

    • Jacobi Symbol Computation (falls back to Legendre for prime moduli)

    • Multiplicative Inverse

    • Extended Euclidean Algorithm

    • Modular Exponentiation

    • Fermat and Miller-Rabin Primality Tests, utility function such as is_prime and next_prime

  • Miscellaneous

    • Root finding over Z

    • Pseudo-random integers

    • Signed and Unsigned comparisons

  • Optimizations

    • Fast Comba based Multiplier, Squaring and Montgomery routines.

    • Montgomery, Diminished Radix and Barrett based modular exponentiation.

    • Karatsuba and Toom-Cook multiplication algorithms.

    • Many pointer aliasing optimiztions throughout the entire library.

Defined Under Namespace

Modules: Version Classes: Bignum, Prime, Specification

Constant Summary collapse

SPEC =
LibTom::Math::Specification.new do |spec|
     spec.name               = "ruby-libtommath"
     spec.version            = LibTom::Math::VERSION
     spec.rubyforge_project  = "copiousfreetime"
     spec.author             = "Jeremy Hinegardner"
     spec.email              = "[email protected]"
     spec.homepage           = "http://copiousfreetime.rubyforge.org/ruby-libtommath/"

     spec.summary            = "Ruby extension for LibTom Math"
     spec.description        = <<-DESC
     ruby-libtommath is a ruby extension encapsulating the LibTomMath multi-precision
     integer library (http://libtom.org/?page=features&newsitems=5&whatfile=ltm).
     
     It has been written to be an almost complete drop in replacement for ruby's 
     Bignum.
     DESC

     spec.extra_rdoc_files   = FileList["README", "CHANGES", "LICENSE"]
     spec.has_rdoc           = true
     spec.rdoc_main          = "README"
     spec.rdoc_options       = [ "--line-numbers" , "--inline-source" ]

     spec.test_files         = FileList["spec/**/*.rb", "test/**/*.rb"]
     spec.files              = spec.test_files + spec.extra_rdoc_files + 
                               FileList["setup.rb", "lib/**/*.rb", "examples/**/*","ext/**/*"] - FileList["ext/**/*.o"]
 
     spec.extensions         << "ext/libtom/mkrf_conf.rb"
     spec.require_paths      << "ext/libtom"
     
     
     # add dependencies
     spec.add_dependency("mkrf", ">= 0.2.2")

     spec.platform           = Gem::Platform::RUBY
     spec.required_rubygems_version = ">= 0.9.5"
 
     spec.remote_user        = "jjh"
     spec.local_rdoc_dir     = "doc/rdoc"
     spec.remote_rdoc_dir    = ""
     spec.local_coverage_dir = "doc/coverage"

     spec.remote_site_dir    = "#{spec.name}/"

end
VERSION =
Version.to_s

Class Method Summary collapse

Class Method Details

.Bignum(a) ⇒ Object

In the vein of other Numeric conversions like Integer(), Rational(), Complex(), Integer(), provide a similar call.



8
9
10
# File 'lib/libtom/math/bignum.rb', line 8

def Bignum(a) 
    LibTom::Math::Bignum.new(a) 
end

.pow2(n) ⇒ Object .two_to_the(n) ⇒ Object

Calculates 2**n and returns the value as a Bignum.



22
23
24
25
26
27
28
29
30
31
32
33
34
# File 'ext/libtom/lt_math.c', line 22

static VALUE ltm_two_to_the(VALUE self, VALUE other)
{
    VALUE result = ALLOC_LTM_BIGNUM;
    mp_int *a    = MP_INT(result);
    int power    = NUM2INT(other);
    int mp_result;
    
    if (MP_OKAY != (mp_result = mp_2expt(a,power))) {
        rb_raise(eLT_M_Error, "Failure calculating 2**%d : %s\n",
            power,mp_error_to_string(mp_result));
    }
    return result;
}

.pow2(n) ⇒ Object .two_to_the(n) ⇒ Object

Calculates 2**n and returns the value as a Bignum.



22
23
24
25
26
27
28
29
30
31
32
33
34
# File 'ext/libtom/lt_math.c', line 22

static VALUE ltm_two_to_the(VALUE self, VALUE other)
{
    VALUE result = ALLOC_LTM_BIGNUM;
    mp_int *a    = MP_INT(result);
    int power    = NUM2INT(other);
    int mp_result;
    
    if (MP_OKAY != (mp_result = mp_2expt(a,power))) {
        rb_raise(eLT_M_Error, "Failure calculating 2**%d : %s\n",
            power,mp_error_to_string(mp_result));
    }
    return result;
}