Skip to content

Decimal arithmetic in Javascript, PHP (with tests against Python's Decimal) using strings for input/output

License

Notifications You must be signed in to change notification settings

eloraburns/StringDecimal

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

64 Commits
 
 
 
 
 
 
 
 
 
 

Repository files navigation

On bounding
===========

The parse operation is bounded in two ways:
1. Numeric expressions without an "e" will consume O(n) in the final representation.
2. Numeric expressions with an "e" will consume O(n+e) in the final representation.

The add operation of an n and m digit pair is bounded by:
1. memory O(3(n+m)), cpu O(2(n+m))

The subtract operation is just the add operation, but currently copies the second argument, so we get:
1. memory O(3(n+m)+m), cpu O(2(n+m))

The multiply operation is implemented with a 2-nested loop:
1. memory O(n+m), cpu O(nm)

The divide operation is implemented in terms of add, subtract, and multiply:
1. (figure this out, but should be bounded)

Bugs
====
* Divide very probably uses more memory than necessary.  Do we need _precision*2 reciprocal digits to guarantee convergence?
* Internal operations shouldn't go back through strings; just pass around internal representations
* Mutations should be avoided
* Prefer passing around whole values instead of an array here and an int there
* Divide iterations could be bounded more tightly; one iteration per digit is probably too much (need to look up the convergence rate guaranteed by the algorithm)

About

Decimal arithmetic in Javascript, PHP (with tests against Python's Decimal) using strings for input/output

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published