About Pnic
Some information about this project.
Pnic's goal is to at least perform the four basic arithmetic operations without directly using the host's arithmetic features. Currently, that host is Bash.
Pnic is a math library for use in Bash scripts. All operations except for shifts are done with string manipulations and lookup tables; they are mostly independent of both Bash's arithmetic[1] and pattern matching[2] features. Thus, Pnic can work on numbers way beyond native limits: over twenty digits in an 8-bit environment.
- Bash's arithmetic feature is used in occupancy conditionals. Substring expansion parameters--for example--are automatically arithmetic in Bash, but Pnic does no such operations in them.
- except for replacing each character with a specified character, for sanity's sake.
Representation
8-bit trillions.
A binary digit (bit) has two symbols: 0 and 1. Eight of them together can produce 256 unique combinations of 0s and 1s. When used to represent numbers zero and onwards, the largest is 255, which is too small in many cases.
Alternatively, a number can also be represented as an array of digits, each of which is addressable by an index of the above representation. In other words, each of the 256 combinations of 0s and 1s corresponds to a digit index. Therefore, the largest number representable this way is 256 digits.[3]
However, this non-native numerical representation means that operators must be implemented in software and run much slower. Memory is required to store those implementations as well as working numbers. Such concerns are secondary to Pnic, and that we recommend those on critical infrastructure to seek low-level solutions instead.
- In practice, this would leave no memory for everything else unless the address space is larger than eight bits.
Operators
Back to school.
Its implementations of addition, subtraction, and multiplication are based on hand algorithms taught during early and middle schools, how these operations are divisible into simpler problems, and how the algorithms are scalable to any real number imaginable.
However, the same can not be said for division, as I am yet to know how a divisor can be split into singular units. Instead, it divides by repeatedly subtracting the divisor from the dividend, padding each with zeros to both improve its runtime and precision.
Comparison and shift operators are added for convenience. While they can be done with the above four, their implementations are independent of them. In particular, the shift operators are bound to Bash's arithmetic limits.
Information on using Pnic and its operators are in the [Documentation] page.
Performance
in big O notation.
Pnic implements operators on top of those built into Bash. Thus, it is slower than lower-level equivalents, which have different use cases than those for Pnic.
Unless otherwise noted, let m be the length of the longer operand, and n be that of the shorter.
- AdditionO(m)
- SubtractionO(m)
- MultiplicationO(mn)
- DivisionO(mp/n) where m is the dividend, n is the divisor, and p is the precision.
- ComparisonO(m)
- ShiftO(n), where n is the distance.
These are very rough estimates with underlying operations unaccounted for. During testing, multiplication performed much slower than the rest. Division can perform even slower with large precision.