A Little arbitrary precision in JavaScript

blame

Status Thu Dec 11 02:27:56 CET 2014

New! Give it a try! Well, the raw bigint/bigrational libraries at least.

The big integer library is nearly complete, with the exception of all of the things I forgot, of course and some optimizations that will follow later. For example: Toom-Cook multiplication/squareing of higher order
I have put the stuff listed below into the sub-directory libs.

A bunch of helper functions
A Bigint library with the following arithmetic functions:
- Addition/Subtraction
- Multiplication and fast multiplication (Karatsuba, Toom-Cook 3, FFT)
- Division and fast division (Burnikel-Ziegler and Newton, Barret division is still broken)
- Squaring and fast Squaring (Karatsuba, Toom-Cook 3, FFT)
- Power (small integer to the power of a bigint and bigint to the power of a small integer)
- Integer logarithm with a positive integer base
- n^th root for positive integer n
- reading and printing the number as a string (a bit slow, no optimizations but see below)
- GCD, LCM and extended GCD
- a bunch of small needful functions (comparing, checking etc.)
A Bigrational library with the following arithmetic functions:
- Addition/Subtraction
- Multiplication/Divison
- n^th root for positive rationals
- median rounding (e.g.: for the roots)
- a lot of helper functions
- Bernoulli numbers. See below for the example
A integer functions library with the following content:
- Factorial, superfactorial, fallingfactorial, risingfactorial, doublefactorial, subfactorial
- Binomial
- Catalan number (not the constant)
- Stirling numbers of the first kind
- Stirling numbers of the second kind
- Bell numbers
- Eulerian (zig) numbers
- Fibonacci
A distinct lack of documentation

The file with the Bigint library is stand-alone, you can give it a try without much ado.

Some optimization for reading and writing big integers are possible, especially the radices base 2^k like 2, 8, 16 and 2²⁶ (the size of the bigint digit).
Optimization of in- and output for radix ten is possible if we work with larger chunks instead of single characters. The input would be much faster (the output not so much but still faster) but needs a big integer library with radix 10^k (with k = 7 for ECMAScript's standard 64-bit numbers).
It (including the basic Bigdecimal code necessary) is in the code but still commented out, needs some more testing.

All what is left to do is to write a basic Bigfloat library (with the same number of functions of the Bigint library) and get the parser to spit out the correct AST.

Bernoulli Numbers

The algorithm is based on: Brent, Richard P., and David Harvey. "Fast computation of Bernoulli, Tangent and Secant numbers." Computational and Analytical Mathematics. Springer New York, 2013. 127-142. Preprint here
Get a Bernoulli number. Please be aware that this is done in pure JavaScript. So B₁₀₀ gets you quasi immediate satisfaction but B_1,000 may need a minute or five.
The algorithm caches the results up to B_n
- Bernoulli Numbers
- Which one?
- How many? One
  All (B_2n including B₁)
- Bernoulli Number(s):
Make Some Typos

A JavaScript port of an older version of the Perl module Lingua::TypoGenerator by Ivan Tubert-Brohman with some additional keyboard layouts
And if you cannot do it yourself, here is a little script to help you out with it.
- Type-O-Mat
- Spelled right:
- Spelled wrong:
- with layout.
It is quite simple and works quite correct for English keyboard layouts, but only so-so for the rest. See the Source code for details. For a more refined algorithm you might look at Lingua::DE::TypoGenerator

Bernoulli Numbers

Type-O-Mat

Needful Links