jtobey / javascript-bignum Goto Github PK

Scheme arithmetic library for JavaScript

License: MIT License

JavaScript 67.01% Shell 0.04% C++ 0.02% C 26.79% Perl 3.03% Makefile 0.29% HTML 2.82%

javascript-bignum's Introduction

Scheme arithmetic library for JavaScript,
https://github.com/jtobey/javascript-bignum.
Copyright (c) 2010, 2011, 2012 John Tobey [email protected]
Copyright (c) 2009 Matthew Crumley [email protected]
Licensed under the MIT license, file LICENSE.
Big integer implementation based on javascript-biginteger,
https://github.com/silentmatt/javascript-biginteger.

#What is it?

The Scheme language supports "exact" arithmetic and mixing exact with inexact numbers. Several basic operations, including add, subtract, multiply, and divide, when given only exact arguments, must return an exact, numerically correct result. They are allowed to fail due to running out of memory, but they are not allowed to return approximations the way ECMAScript operators may.

For example, adding exact 1/100 to exact 0 one hundred times produces exactly 1, not 1.0000000000000007 as in JavaScript. Raising 2 to the 1024th power returns a 308-digit integer with complete precision, not Infinity as in ECMAScript.

This implementation provides all functions listed in the R6RS (I recommend the PDF) Scheme specification, Section 11.7, along with eqv? from Section 11.5. (eqv? uses JavaScript's === to compare non-numbers.)

Exact numbers support the standard ECMA Number formatting methods (toFixed, toExponential, and toPrecision) without a fixed upper limit to precision.

#Implementation Details

This release contains a plugin API designed to support alternative implementations of four broad types: exact integer, exact rational, inexact real, and complex. The plugin API is under heavy development and neither complete nor documented. A multiple dispatch system supports specialization of basic operations by any operands' types.

Exact integers of absolute value less than 2 to the 53rd power (9,007,199,254,740,992 or about 9e15) are represented as native numbers. Outside this range, exact integers are represented as BigInteger objects: arrays base 10000000 with sign flag.

Exact rationals are represented as pairs of exact integers (numerator, denominator) in lowest terms.

Non-real complex numbers are represented in rectangular coordinates, either both exact or both inexact.

Inexact real numbers are represented as native numbers, wrapped to provide a method space without affecting the standard Number.prototype object.

Number objects may contain properties and methods other than the standard toString, toFixed, etc. Such properties have names beginning with _ or SN_. They are private to the library, and applications should not use them. The Scheme functions are not methods of number objects.

#Similar Projects

Danny Yoo's Whalesong (http://hashcollision.org/whalesong/), a Racket (Scheme) to JavaScript compiler with its own Scheme numeric tower called js-numbers (https://github.com/dyoo/js-numbers).
Leemon Baird's big integer library (http://www.leemon.com/crypto/BigInt.js).
HOP (http://hop.inria.fr/), a framework containing a Scheme-to-JS compiler that did NOT implement the numeric tower as of 2011.
node-gmp (https://github.com/postwait/node-gmp), node.js bindings for the GNU Multiple Precision Arithmetic Library.
bignumber.js (https://github.com/MikeMcl/bignumber.js)
strint (https://github.com/rauschma/strint), a JavaScript library for string-encoded integers.
Any others out there???

#Installation

Copy biginteger.js and schemeNumber.js from this directory to your Web or JavaScript directory. Load biginteger.js first, then schemeNumber.js.

#Usage

See documentation in schemeNumber.js, or view it on the Web at http://john-edwin-tobey.org/Scheme/javascript-bignum/docs/files/schemeNumber-js.html, or try to extract it to HTML using NaturalDocs and the build-docs script in this directory.

#Changes

1.3.0 (unstable) - 2012-03-07

* Unstable development branch containing new plugin API.

1.2.0 - 2012-03-04 - Current stable release based on 1.1.x.

1.1.5 (unstable) - 2012-03-01

* Fixed parser bug affecting numbers like "#e.021".

1.1.2 (unstable) - 2011-03-19

* Do not modify the standard Number.prototype object.

1.0.1 - 2011-02-10 - First numbered release.

See file CHANGES.md for more.

javascript-bignum's People

Contributors

Stargazers

Watchers

javascript-bignum's Issues

Minor errors found by Google Closure Compiler

schemeNumber.js line 202: trailing comma is unnecessary
schemeNumber.js line 208: same thing
schemeNumber.js line 2394: forgot to define f

GCD is broken/poorly documented

https://github.com/jtobey/javascript-bignum/blob/master/lib/leemonBigInt.js#L903

I've been trying to implement Pollard's Rho algorithm as part of a demonstration of ElGamal. While testing it, I determined that the GCD function sometimes doesn't return the expected results. For example:

GCD([23018,1,0],[17454,0,0])
[2, 0, 0]
GCD([17454,0,0],[23018,1,0])
[14, 0, 0]

According to http://cacr.uwaterloo.ca/hac/about/chap14.pdf, Lehmer's gcd algorithm imposes x >= y as a condition. Since the condition is not documented in the code, I'm not sure if there are other problems with it.

If not, the condition should probably be documented for GCD_. Perhaps GCD should be changed to pass the larger of x and y as the first parameter of the GCD_ call.

problem with number not being finite.

Hi @jtobey ,

This error is being raised:

Error: SchemeNumber: &assertion: div/mod first argument is not finite: +inf.0

I'm doing this in my code where the error happens:

        // let y = x^((p-1)/2) mod p
        var y = fn.mod( fn.expt(x, fn['/']( fn['-'](p, 1), 2 ) ), p );

x is a random integer anywhere between 1 and 160 bits long, and p is 160 bits long (after dropping the leading zeros).

I looked at the schemeNumber.js source (the error is raised on line 2629), but haven't gotten to fully understand it yet.

Why might I be seeing this error? Is there a size limit for schemeNumbers at which point the library gives up representing it's value? Is there a memory usage limit?

Usage examples?

I see the docs at http://john-edwin-tobey.org/Scheme/javascript-bignum/docs/files/schemeNumber-js.html but it's not as helpful as it could be if there were some usage examples.

Could you provide some usage examples? A nice place to put them would be in the project's readme file.

Negative inexact raised to a power

I believe the following illustrates some undesirable behavior.

   var sn = SchemeNumber;
   var a = sn('#i-1');
   var p = sn('1');
   var result = sn.fn['expt'](a, p);
   console.log(a + "^" + p + " = " + result);
   console.log(a + "^" + p + " = " + result.toString());

Raising an inexact negative number to a (non-complex) power results in a complex number.
And, printing this number gives NaN unless the toString method is explicitly called.

Suggestion for behavior of SchemeNumber.maxIntegerDigits.

Setting this value to allow exponentiation to be bigger is a nice feature.

My suggestion is to let users assign schemeNumbers or Infinity to the value of SchemeNumber.maxIntegerDigits to have better control over it.

For example, let users do things like:

SchemeNumber.maxIntegerDigits = Infinity;

SchemeNumber.maxIntegerDigits = SchemeNumber("100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000");

A value of Infinity would (obviously) mean no limit, while a schemeNumber value would allow for limits larger than what can be specified with native JS values.

Any others out there? -- Yes

You forgot to add "bignumber.js"

https://github.com/MikeMcl/bignumber.js

It's painfully easy to use, and comes with great docs so please add it.

Disclaimer: I am not the author of that lib, nor in any way work for them. I just wanted to complete the list of all the arbitrary-precision libs in JS.

Does this support the modulus operation?

For example a%b?

Big numbers not working after 18 bits of size.

I'm trying to implement my own modpow function, and the SchemeNumber.maxIntegerDigits seems to be the limiting factor. Removing the check altogether for the expt function where the "first argument is not finite" error gets raised on line 2629 allows me to continue.

But I'm not getting the results that I expect. If the numbers are smaller, it works, but if the number are bigger but still smaller than 2^53, then it doesn't (but I have plenty of memory).

Here's my function:

function modpow(x, y, n) {
    // I'm passing in strings or schemeNumbers, no natives.
    x = SchemeNumber(x);
    y = SchemeNumber(y);
    n = SchemeNumber(n);
    var result = 1;
    var binaryRepresentationOfExponent = y.toString(2);

    for (var i=0; i<binaryRepresentationOfExponent.length; i++) {
        if (binaryRepresentationOfExponent.charAt(i) == '1') {
            result = fn.mod( fn["*"]( fn['*'](result, result), x), n);
        }
        else {
            result = fn.mod( fn['*'](result, result), n);
        }
    }

    log(" -- "+x.toString(10)+"^"+y.toString(10)+" mod "+n.toString(10)+" RESULT: " + result.toString(10));
    return result;
}

For example, check out the following outputs of calling my function in a loop, one with small numbers (20 bits or less), one with slightly bigger numbers (25 bits or less) and one with numbers of 30 bits or less (not, all of these numbers are schemeNumbers and they are smaller than the native limit of 2^53):

20 bits:

These ones all work fine:

 -- 139730^394726 mod 789453 RESULT: 501337
 -- 726593^479350 mod 958701 RESULT: 57265
 -- 1026907^396933 mod 793867 RESULT: 792128
 -- 891615^442377 mod 884755 RESULT: 120355
 -- 112542^396142 mod 792285 RESULT: 471156
 -- 538465^514881 mod 1029763 RESULT: 847136
 -- 299308^317502 mod 635005 RESULT: 508104
 -- 131778^394712 mod 789425 RESULT: 208716
 -- 992979^509016 mod 1018033 RESULT: 497588
 -- 987591^417173 mod 834347 RESULT: 73920
 -- 668295^395936 mod 791873 RESULT: 789448
 -- 985849^319283 mod 638567 RESULT: 496576
 -- 403846^378031 mod 756063 RESULT: 238681
 -- 165749^316859 mod 633719 RESULT: 125256
 -- 564165^316539 mod 633079 RESULT: 2156
 -- 107509^479499 mod 958999 RESULT: 506072
 -- 697732^495804 mod 991609 RESULT: 912263
 -- 438769^460206 mod 920413 RESULT: 617465
 -- 505279^284142 mod 568285 RESULT: 209211
 -- 145994^426064 mod 852129 RESULT: 717886
 -- 965249^314503 mod 629007 RESULT: 202976
 -- 275169^482295 mod 964591 RESULT: 23600
 -- 303617^445877 mod 891755 RESULT: 454762

25 bits:

 -- 12565866^8783384 mod 17566769 RESULT: 0
 -- 5421817^12289774 mod 24579549 RESULT: 0
 -- 16398908^13503319 mod 27006639 RESULT: 23855104
 -- 3835155^8520408 mod 17040817 RESULT: 14943832
 -- 6718190^12492678 mod 24985357 RESULT: 0
 -- 1412017^12781916 mod 25563833 RESULT: 18176812
 -- 2047445^10608139 mod 21216279 RESULT: 7553024
 -- 12987550^12585703 mod 25171407 RESULT: 20447232
 -- 21146329^13189640 mod 26379281 RESULT: 0
 -- 8139549^12765618 mod 25531237 RESULT: 21980557
 -- 12431709^14369855 mod 28739711 RESULT: 524288
 -- 1152460^16719699 mod 33439399 RESULT: 19005440
 -- 30056251^11849436 mod 23698873 RESULT: 6104173
 -- 32738224^8965879 mod 17931759 RESULT: 0
 -- 20909850^9929454 mod 19858909 RESULT: 12262975
 -- 13969680^9897159 mod 19794319 RESULT: 15728640
 -- 6306037^13763788 mod 27527577 RESULT: 8555211
 -- 12495844^9082092 mod 18164185 RESULT: 11661601
 -- 18876918^11324268 mod 22648537 RESULT: 5523566
 -- 30256478^10196847 mod 20393695 RESULT: 12845056
 -- 6631520^12079300 mod 24158601 RESULT: 23659506

30 bits:

 -- 10270590^356681627 mod 713363255 RESULT: 0
 -- 498866520^472848363 mod 945696727 RESULT: 0
 -- 144969034^278959505 mod 557919011 RESULT: 0
 -- 311114789^456869444 mod 913738889 RESULT: 0
 -- 207729674^366380073 mod 732760147 RESULT: 0
 -- 24903887^509070672 mod 1018141345 RESULT: 0
 -- 534190065^375754658 mod 751509317 RESULT: 0
 -- 305637^317606645 mod 635213291 RESULT: 419430400
 -- 59483847^473175270 mod 946350541 RESULT: 0
 -- 281579956^313280274 mod 626560549 RESULT: 0
 -- 264150281^297390241 mod 594780483 RESULT: 0
 -- 36209975^276812543 mod 553625087 RESULT: 0
 -- 409668651^393514895 mod 787029791 RESULT: 0
 -- 406661344^283252541 mod 566505083 RESULT: 0
 -- 450666631^398508318 mod 797016637 RESULT: 0
 -- 288335035^320166021 mod 640332043 RESULT: 0
 -- 524629248^518357032 mod 1036714065 RESULT: 0
 -- 155879269^460687891 mod 921375783 RESULT: 0
 -- 56080000^421577698 mod 843155397 RESULT: 0

As you can see, the bigger the numbers get, then the results start to be 0. At around 500 bits, the results start to be NaN instead of 0.

WHat I did was comment out the following (line 2628):

            //if (!SN_isFinite(x))
                //raise("&assertion", "div/mod first argument is not finite", x);

I also tried setting SchemeNumber.maxIntegerDigits = 1e1000000000000; without uncommenting those two lines, but it'd still complain about argument one not being finite.

Might I be doing something wrong in my code? Do I need to do something to lift size restrictions?

Problem with node 0.10

Installs OK:

peter@Virtual:~/Dropbox/git/enode$ npm install bignum
npm http GET https://registry.npmjs.org/bignum
npm http 304 https://registry.npmjs.org/bignum

> [email protected] install /home/peter/node_modules/bignum
> node-gyp configure build

make: se ingresa al directorio «/home/peter/node_modules/bignum/build»
  CXX(target) Release/obj.target/bignum/bignum.o
  SOLINK_MODULE(target) Release/obj.target/bignum.node
  SOLINK_MODULE(target) Release/obj.target/bignum.node: Finished
  COPY Release/bignum.node
make: se sale del directorio «/home/peter/node_modules/bignum/build»
[email protected] ../../../node_modules/bignum

But why I try to use it I get an error:

$ node
> var big = require('bignum');
Error: Symbol bignum_module not found.
    at Module.load (module.js:356:32)
    at Function.Module._load (module.js:312:12)
    at Module.require (module.js:364:17)
    at new require (module.js:380:17)
    at Object.<anonymous> (/home/peter/node_modules/bignum/index.js:4:14)
    at Module._compile (module.js:456:26)
    at Object.Module._extensions..js (module.js:474:10)
    at Module.load (module.js:356:32)
    at Function.Module._load (module.js:312:12)
    at Module.require (module.js:364:17)

I'm using Ubuntu Linux 64bit