{"_id":"@cursorsdottsx/infint","_rev":"1-8334ed0306c0637d3546307ce7331c65","name":"@cursorsdottsx/infint","dist-tags":{"latest":"1.0.0"},"versions":{"1.0.0":{"name":"@cursorsdottsx/infint","version":"1.0.0","description":"Lightning-fast arbitrary precision integers using strings + walkthrough and explanation.","main":"dist/index.js","scripts":{"test":"echo \"Error: no test specified\" && exit 1"},"repository":{"type":"git","url":"git+https://github.com/cursorsdottsx/infint.git"},"devDependencies":{"@types/node":"^17.0.8","typescript":"^4.5.0"},"keywords":["infint","bigint","big integer","big number","arbitrary precision"],"author":{"name":"cursorsdottsx","email":"cursors.dev@gmail.com"},"license":"MIT","bugs":{"url":"https://github.com/cursorsdottsx/infint/issues"},"homepage":"https://github.com/cursorsdottsx/infint#readme","dependencies":{},"gitHead":"1071e658fd397bce3b55e15a51be38a82a71771c","_id":"@cursorsdottsx/infint@1.0.0","_nodeVersion":"14.11.0","_npmVersion":"7.6.3","dist":{"integrity":"sha512-6FN+/Zy41d+hQCvkqWrpxKPILcpxZkkaOzFd70koWHaFX2RC8S9aYiCw7DA7ExF/m+tHh13oBNc+i/4au8i48Q==","shasum":"170f229f39bf04c8fb1e2f79c5a66c507528ecca","tarball":"https://registry.npmjs.org/@cursorsdottsx/infint/-/infint-1.0.0.tgz","fileCount":5,"unpackedSize":24057,"npm-signature":"-----BEGIN PGP SIGNATURE-----\r\nVersion: OpenPGP.js v3.0.13\r\nComment: https://openpgpjs.org\r\n\r\nwsFcBAEBCAAQBQJh5C95CRA9TVsSAnZWagAABiQP/jOxUBbZVnZQYRZVlWJ1\nzISmzMQxUdLa6DASpQ2j8ZO/4xfbp9nWTj7BTtbLGAbApSPTp5GGDtlmtbvJ\n/vF9OJeu5yjoWHoevqVI3L8Jd4HXlBkFpHAIJ4LwgNeNzWgHxa7FjiiUqorG\nGmnqpvXZy/G10w1SAAxtiLXRbjlDJxvi5xbLtRjFTy+E0jHinCe7oYreS3/4\nCkNX0um8k2I1nXQvMEuC1Dp+16cfRmiXmxUumT7kVZqOe3mHm9VOn2zNF5X8\n/edDksDZ5urQwqK9UF7Xd7HQHNra0foTdSRL1zVS1beOwDpELgO0eJR7bbUr\ntR3+9jY2Sc3R7RPZbW/8Zd2W3o9IH1ySQz1RRzBjGR/7P+GWIN1yvS84oTA8\nTI+JjFrr4HhBEQ+7fYiTivSfAZC7m6Y8jN/tiJ5u1XPZu9Ps+K7IZr8vTU3P\n1EZhjvmdsO4LJh9XNnmUgE1Igid/95goMRAtt1j6dnb+OLyH4yJsPcCj/qqE\nIsTZFeuouFQPd0HIfvyq57rHLVtPrRPf99fUtrhkg9JY/kHuRvoWmyYVSuwN\nT2q7vKtiJ8CPfuV4LSJmn1dv0AP+OepzR72tP/oNiTB5VPr4BKkEnytxjvE6\noLDv+JGiMBmKrKFJkaoCco+NJnErXN/dC4aXSaiiKupVtvcDRUrZY7XjY8wv\nImVR\r\n=lMSK\r\n-----END PGP SIGNATURE-----\r\n","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIQD6o2RgSDyXp2pb6qU2c75ACtiVgCd0gPH5+/fsEdYf7gIgN+9ScIY9Xdug1nT+paybZBQfgJBtRXBu7FE8FLI+pr0="}]},"_npmUser":{"name":"cursorspkg","email":"cursors.dev@gmail.com"},"directories":{},"maintainers":[{"name":"cursorsdev","email":"cursors.alt@gmail.com"},{"name":"cursorspkg","email":"cursors.dev@gmail.com"}],"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/infint_1.0.0_1642344313760_0.04569937083680187"},"_hasShrinkwrap":false}},"time":{"created":"2022-01-16T14:45:13.711Z","1.0.0":"2022-01-16T14:45:13.910Z","modified":"2022-04-05T02:20:39.505Z"},"maintainers":[{"name":"cursorsdev","email":"cursors.alt@gmail.com"},{"name":"cursorspkg","email":"cursors.dev@gmail.com"}],"description":"Lightning-fast arbitrary precision integers using strings + walkthrough and explanation.","homepage":"https://github.com/cursorsdottsx/infint#readme","keywords":["infint","bigint","big integer","big number","arbitrary precision"],"repository":{"type":"git","url":"git+https://github.com/cursorsdottsx/infint.git"},"author":{"name":"cursorsdottsx","email":"cursors.dev@gmail.com"},"bugs":{"url":"https://github.com/cursorsdottsx/infint/issues"},"license":"MIT","readme":"# `infint`\n\n```\nLightning-fast arbitrary precision integers using strings + walkthrough and explanation.\n\nSupported operations:\n\n- Addition\n- Subtraction\n- Multiplication\n- Exponentiation\n- Division\n- Modulo\n- Greatest common divisor\n- Least common multiple\n- N-th root\n\nAlgorithms used:\n\n- Grade-school addition\n- Grade-school subtraction\n- Grid multiplication\n- Exponentiation by squaring\n- Long division\n- Long division with remainder\n- Euclidean algorithm\n- Derived by definition\n- Shifting n-th root algorithm\n\n```\n\n```\n/**\n * ---------------------------------------------------------\n *   I N F I N I T E   P R E C I S I O N   I N T E G E R S\n * ---------------------------------------------------------\n * \n * = A b o u t =============================================\n * \n * In the olden days of JavaScript, we were limited by\n * only the precision of extremely large numbers. Either\n * sacrifice accuracy for convenience, or sacrifice\n * convenience for accuracy. Now that we have BigInt and\n * a plethora of libraries for arbitrary precision\n * numbers, it is a rather trivial problem.\n * \n * So why re-invent the wheel and write another library\n * to implement arbitrary precision in JavaScript?\n * \n * First, this is strictly only integers. There is no\n * support for decimals and fractions. Because it is\n * strictly integers it will be slightly faster than\n * implementations supporting other types of numbers.\n * \n * Second, it uses modern language features with\n * TypeScript, unlike some other libraries written\n * with the unfriendly var keyword.\n * \n * Third, this also supports other common operations, not\n * just simple grade school arithmetic. Note that these\n * are naturally more computationally expensive.\n * \n * Fourth, the implementation uses fast algorithms\n * and is fast enough for most applications\n * using arbitrary precision integers. Some aspects\n * of the algorithms have been replaced by slower\n * alternatives for readability and to follow the\n * notes below.\n * \n * Enjoy true infinite precision integers now.\n * \n * = N o t e s =============================================\n * \n * Addition is rather trivial if we only consider positive \n * integers. However, if we want to support negative\n * integers then implementing proper subtraction would\n * greatly reduce the effort required.\n * \n * Subtraction is also trivial, but not as trivial, if \n * we only consider positive integers, and the minuend is \n * greater than the subtrahend.\n * \n * The complicated part of true subtraction is that\n * the signs of the numbers influence the sign of the\n * output. This can be easily simplified because of\n * how subtraction can be thought of as adding a \n * negative number.\n * \n * And so we list all possible cases:\n * \n *   a > b & +a +b => a - b      |  22 - 13  => 22 - 13\n *   a < b & +a +b => -(b - a)   |  13 - 22  => -(22 - 13)\n *   - - - & +a -b => a + b      |  13 - -22 => 13 + 22\n *   - - - & -a +b => -(-a + b)  | -13 - 22  => -(13 + 22)\n *   a > b & -a -b => b - a      | -13 - -22 => 22 - 13\n *   a < b & -a -b => -(-a - -b) | -22 - -13 => -(22 - 13)\n * \n * After implementing all the cases and then simplifying\n * the resulting code greatly, we now have true subtraction\n * which supports both negative and positive numbers.\n * \n * For multiplication we will use the extremely simple\n * grid method, in which you split up the multiplicand and\n * multiplier into their respective place values and align\n * them on a grid, like so:\n * \n *   +-----+-----+-----+\n *   | xxx |  20 |   2 |\n *   +-----+-----+-----+\n *   |  10 | 200 |  20 |\n *   +-----+-----+-----+\n *   |   3 |  60 |   6 |\n *   +-----+-----+-----+\n * \n * Then it's just an addition of all the cells in the grid.\n * This should be slightly faster and easier to implement\n * than traditional grade school multiplication.\n * \n * The only expensive computation here is the splitting and\n * finding combonations of the place values.\n * \n * Now for the inverse of multiplication, division.\n * \n * Since we are using only integers, we are going to\n * implement integer division. The simplest way to implement\n * unsigned integer division would be a while loop with\n * repeated subtraction.\n * \n * Obviously because we are dealing with extremely large\n * numbers, this would be too slow to perform.\n * \n * Instead we will vie for a simple implementation\n * of traditional long division. Here is our example:\n * \n *      +------\n *   13 | 2213\n * \n * We first need to take the first two digits of the dividend\n * because the divisor is two digits.\n * Then we check if the divisor is greater than the two digits.\n * \n * In this case it isn't, so we are free to continue. Next,\n * we use naive integer division because it will not be slow\n * when used with operands of similar magnitude.\n * \n * With our example, we get the quotient 1:\n * \n *        1\n *      +------\n *   13 | 2213\n * \n * And then we subtract 13 from the two digits, but what\n * that is actually doing is subtracting 1300 from the entire\n * dividend.\n * \n *        1\n *      +------\n *   13 | 2213\n *      - 1300\n *         913\n * \n * We then repeat these steps with our new dividend.\n * \n *        17\n *      +------\n *   13 | 2213\n *      - 1300\n *         913\n *      -  910\n *           3\n * \n * One step later and we have another dividend. However,\n * this time, the dividend is smaller than the divisor,\n * which marks the end of division. \n * \n * Our quotient is left, 17, and we can clearly see that\n * the remainder is 3.\n * \n * With division, we can now easily implement modulo.\n * \n * The code is exactly the same, but with a few different\n * edge cases to check for at the beginning. Note that \n * we could also instead use an efficient modulus \n * algorithm, but for the sake of brevity it is not \n * used.\n * \n * Exponentiation is next. A naive implementation might \n * use a loop and multiply the number by itself inside\n * the loop. Remember that we are using arbitrary\n * precision integers and that the integers will be\n * extremely large.\n * \n * So, we cannot use a plain loop. The optimization we \n * observe and utilize is exponentiation by squaring.\n * \n * The core concept is that:\n * \n *   if x is even\n *     \n *     a^x = a^(x / 2) * a^(x / 2)\n * \n *   if x is odd \n * \n *     a^x = a^((x - 1) / 2) * a^((x - 1) / 2) * a\n * \n * Because we are squaring, we need less computations\n * to find the result. For example, if 36 was x and\n * 2 was the base:\n * \n *   36 is even \n * \n *   2^36 = 2^18 * 2^18\n * \n *   18 is even\n *  \n *   2^18 = 2^9 * 2^9\n * \n *   9 is odd \n * \n *   2^9 = 2^4 * 2^4 * 2\n *   \n *   4 is even\n * \n *   2^4 = 2^2 * 2^2\n * \n *   2 is even \n * \n *   2^2 = 2^1 * 2^1\n * \n * Compared to 36 multiplications with the simple loop,\n * exponentiation by squaring is considerably more \n * efficient.\n * \n * The next functions we will implement are lcm and gcd,\n * more commonly known as least common multiple and \n * greatest common divisior.\n * \n * Since lcm can be computed much more easily using gcd,\n * we will implement gcd first. It is common knowledge \n * that Euclid's algorithm is quite fast and easy to \n * implment, so that is what we will use. \n * \n * Now that we can use the gcd function, we can compute \n * the least common multiple as follows:\n * \n *   lcm(a, b) = a * b / gcd(a, b)\n * \n * Which should be trivial to write code for.\n * \n * Finally, we have our roots to calculate. Because there\n * is a general algorithm to get the nth root, we will \n * instead implement the algorithm, named the shifting\n * nth root algorithm.\n * \n * Even if we are using an algorithm for all indices,\n * it is worth to take note of the Newton-Raphson\n * method to approximate roots very closely, although \n * it does not work well for larger indices as it becomes\n * harder to find an initial guess that will require\n * little iterations.\n * \n * This last algorithm is quite long and requires rather\n * more number theory and mathematics, so be prepared.\n * \n * We first define a few variables: let n be the degree\n * of the root, x be the radicand, y be the root, and \n * r be the remainder.\n * \n * Let x' be the value of x in the next iteration,\n * and y' and r' in the same manner.\n * \n * Now for the actual algorithm. Split the radicand\n * into chunks of digits, each with the length as the \n * degree of the root. Align the chunks so that the \n * decimal place is between them. \n * \n * Take the first chunk, alpha, and find beta, so that\n * \n *   beta ^ n <= alpha\n * \n * Then set y equal to beta, and r to\n *   \n *   alpha - beta ^ n\n * \n * beause it is the remainder.\n * \n * You an think of this as a very general approximation\n * of the root. The next step is to iterate over each \n * of the remaining chunks, where each chunk will be \n * henceforth referred to as alpha.\n * \n * Find beta such that\n * \n *   (10 ^ y + beta) ^ n - 10 ^ n * y ^ x <= 10 ^ n * r + alpha\n * \n * This will give us the next digit of the root, beta.\n * So in the next iteration, we will append our newfound \n * digit to the answer.\n * \n *   y' = 10 ^ y + beta\n *\n *   r' = 10 ^ n * r + alpha - (y' ^ x - 10 ^ x * y ^ x)\n *\n * And we also calculate the new remainder to be used for the \n * next iteration. Now before the next iteration, we update \n * the values of y and r with y' and r', respectively.\n * \n * Repeat this process until you have reached the desired\n * precision or when you have iterated through all chunks.\n * \n * This algorithm is easy enough to implement with our existing\n * operations from above.\n * \n * = C r e d i t s =========================================\n * \n * \"Give credit where credit is due.\"\n * \n * https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic\n * \n * https://cheonhyangzhang.gitbooks.io/leetcode-solutions/content/415-add-strings.html\n * https://www.geeksforgeeks.org/sum-two-large-numbers/\n * \n * https://stackoverflow.com/questions/40708444/add-or-subtract-two-numbers-represented-as-strings-without-using-int-double-lo\n * https://www.geeksforgeeks.org/difference-of-two-large-numbers/\n *\n * https://en.wikipedia.org/wiki/Multiplication_algorithm\n * \n * https://en.wikipedia.org/wiki/Division_algorithm\n * https://en.wikipedia.org/wiki/Long_division\n * \n * https://en.wikipedia.org/wiki/Euclidean_algorithm \n *\n * https://stackoverflow.com/questions/101439/the-most-efficient-way-to-implement-an-integer-based-power-function-powint-int\n * https://en.wikipedia.org/wiki/Exponentiation_by_squaring\n * \n * https://en.wikipedia.org/wiki/Nth_root\n * https://stackoverflow.com/questions/20730053/algorithm-to-find-nth-root-of-a-number\n * https://en.wikipedia.org/wiki/Shifting_nth_root_algorithm\n * https://math.stackexchange.com/questions/1066790/shifting-nth-root-algorithm\n */\n ```\n","readmeFilename":"README.md"}