{"id":1632,"date":"2015-01-16T22:04:09","date_gmt":"2015-01-17T04:04:09","guid":{"rendered":"https:\/\/justinparrtech.com\/JustinParr-Tech\/?p=1632"},"modified":"2015-10-23T10:14:01","modified_gmt":"2015-10-23T15:14:01","slug":"an-algorithm-for-arbitrary-precision-integer-division","status":"publish","type":"post","link":"https:\/\/justinparrtech.com\/JustinParr-Tech\/an-algorithm-for-arbitrary-precision-integer-division\/","title":{"rendered":"An Algorithm for Arbitrary Precision Integer Division"},"content":{"rendered":"<p>I was working on a project that required simple arithmetic for very large integers, a set of algorithms called &#8220;Arbitrary Precision Math&#8221;.<\/p>\n<p>Thinking back to elementary school, simple algorithms exist for addition, subtraction, and multiplication of two numbers with any number of digits.<\/p>\n<p>To my surprise, every algorithm for division either relies on logarithms, which are difficult to implement in arbitrary precision, or the first instruction was &#8220;guess the first number, then guess the second number&#8221; etc&#8230;<\/p>\n<p><strong>Update: 10\/2015:<\/strong>\u00a0 I&#8217;ve put together a YouTube video for this post.\u00a0 Check it out, here:<\/p>\n<p align=\"center\"><iframe loading=\"lazy\" src=\"https:\/\/www.youtube.com\/embed\/6bpLYxk9TUQ\" width=\"600\" height=\"450\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n<p>&nbsp;<\/p>\n<p>Read on, for a simple, reliable, repeatable algorithm for dividing integers of any length.<\/p>\n<p>&nbsp;<\/p>\n<p><!--more--><\/p>\n<p>&nbsp;<\/p>\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_81 counter-hierarchy ez-toc-counter ez-toc-custom ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\"><p class=\"ez-toc-title\" style=\"cursor:inherit\">Table of Contents<\/p>\n<\/div><nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/justinparrtech.com\/JustinParr-Tech\/an-algorithm-for-arbitrary-precision-integer-division\/#background\" >Background<\/a><ul class='ez-toc-list-level-3' ><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/justinparrtech.com\/JustinParr-Tech\/an-algorithm-for-arbitrary-precision-integer-division\/#what-is-arbitrary-precision-math\" >What is Arbitrary Precision Math?<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/justinparrtech.com\/JustinParr-Tech\/an-algorithm-for-arbitrary-precision-integer-division\/#what-is-division\" >What is Division?<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/justinparrtech.com\/JustinParr-Tech\/an-algorithm-for-arbitrary-precision-integer-division\/#finding-the-first-digit\" >Finding the First Digit<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/justinparrtech.com\/JustinParr-Tech\/an-algorithm-for-arbitrary-precision-integer-division\/#process-overview\" >Process Overview<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/justinparrtech.com\/JustinParr-Tech\/an-algorithm-for-arbitrary-precision-integer-division\/#algorithm-and-detailed-walkthrough\" >Algorithm and Detailed Walkthrough<\/a><ul class='ez-toc-list-level-3' ><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/justinparrtech.com\/JustinParr-Tech\/an-algorithm-for-arbitrary-precision-integer-division\/#algorithm\" >Algorithm<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-8\" href=\"https:\/\/justinparrtech.com\/JustinParr-Tech\/an-algorithm-for-arbitrary-precision-integer-division\/#walk-through-%e2%80%93-how-does-this-work\" >Walk Through &#8211; How does this work?<\/a><ul class='ez-toc-list-level-4' ><li class='ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-9\" href=\"https:\/\/justinparrtech.com\/JustinParr-Tech\/an-algorithm-for-arbitrary-precision-integer-division\/#start-of-loop\" >Start of Loop<\/a><\/li><\/ul><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-10\" href=\"https:\/\/justinparrtech.com\/JustinParr-Tech\/an-algorithm-for-arbitrary-precision-integer-division\/#examples\" >Examples<\/a><ul class='ez-toc-list-level-3' ><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-11\" href=\"https:\/\/justinparrtech.com\/JustinParr-Tech\/an-algorithm-for-arbitrary-precision-integer-division\/#example-1\" >Example 1<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-12\" href=\"https:\/\/justinparrtech.com\/JustinParr-Tech\/an-algorithm-for-arbitrary-precision-integer-division\/#example-2\" >Example 2<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-13\" href=\"https:\/\/justinparrtech.com\/JustinParr-Tech\/an-algorithm-for-arbitrary-precision-integer-division\/#corollary-in-base-x\" >Corollary in Base X<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-14\" href=\"https:\/\/justinparrtech.com\/JustinParr-Tech\/an-algorithm-for-arbitrary-precision-integer-division\/#summary\" >Summary<\/a><\/li><\/ul><\/nav><\/div>\n\n<p>&nbsp;<\/p>\n<h2><span class=\"ez-toc-section\" id=\"background\"><\/span>Background<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>&nbsp;<\/p>\n<h3><span class=\"ez-toc-section\" id=\"what-is-arbitrary-precision-math\"><\/span>What is Arbitrary Precision Math?<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<p>Computers store numbers based on a variable&#8217;s data type, and the data type determines the largest number that you can store:<\/p>\n<table border=\"0\" cellspacing=\"0\">\n<colgroup width=\"85\"><\/colgroup>\n<colgroup span=\"2\" width=\"102\"><\/colgroup>\n<colgroup width=\"176\"><\/colgroup>\n<colgroup width=\"183\"><\/colgroup>\n<tbody>\n<tr>\n<td align=\"LEFT\" height=\"17\"><strong>Bits<\/strong><\/td>\n<td align=\"LEFT\"><strong>Bytes<\/strong><\/td>\n<td align=\"LEFT\"><strong>Data Type<\/strong><\/td>\n<td align=\"LEFT\"><strong>Largest Signed Integer<\/strong><\/td>\n<td align=\"LEFT\"><strong>Largest Unsigned Integer<\/strong><\/td>\n<\/tr>\n<tr>\n<td align=\"RIGHT\" height=\"17\">8<\/td>\n<td align=\"RIGHT\">1<\/td>\n<td align=\"LEFT\">Byte<\/td>\n<td align=\"RIGHT\">127<\/td>\n<td align=\"RIGHT\">255<\/td>\n<\/tr>\n<tr>\n<td align=\"RIGHT\" height=\"17\">16<\/td>\n<td align=\"RIGHT\">2<\/td>\n<td align=\"LEFT\">Int (Word)<\/td>\n<td align=\"RIGHT\">32,767<\/td>\n<td align=\"RIGHT\">65,535<\/td>\n<\/tr>\n<tr>\n<td align=\"RIGHT\" height=\"17\">32<\/td>\n<td align=\"RIGHT\">4<\/td>\n<td align=\"LEFT\">Long (D-Word)<\/td>\n<td align=\"RIGHT\">2,147,483,647<\/td>\n<td align=\"RIGHT\">4,294,967,295<\/td>\n<\/tr>\n<tr>\n<td align=\"RIGHT\" height=\"17\">64<\/td>\n<td align=\"RIGHT\">8<\/td>\n<td align=\"LEFT\">Int64 (Q-Word)<\/td>\n<td align=\"RIGHT\">9,223,372,036,854,780,000<\/td>\n<td align=\"RIGHT\">18,446,744,073,709,600,000<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>Notice the trailing zeros for the Int64 data type &#8211; the program I used to perform the calculation doesn&#8217;t have enough precision to calculate the actual digits, resulting in rounding errors!<\/p>\n<p>Being able to represent any 18-digit number is fairly impressive, if you have a compiler and operating system that support the Int64 data type.<\/p>\n<p>What if you need 20 digits? \u00a0Or 100 digits?<\/p>\n<p>Although you could implement an arbitrary-precision library using strings, this is increasingly inefficient as the number of digits increases, because each digit requires a whole byte to encode.<\/p>\n<p>A better solution is to create a multi-segment string, whose segments are each one of the base integer data types. \u00a0For example, a 16-bit Int can represent any base-10 4-digit number: 0000 through 9999. \u00a0Let&#8217;s say you have a data type and custom library that implements a string of Ints, up to 30 positions. \u00a0This custom data type can represent an unsigned number up to 30 * 4, or 120 digits in length!<\/p>\n<p>Just as you can represent extremely long integers using arbitrary-precision math, you can represent long strings of decimal digits as well, because you can choose where to put the decimal point.<\/p>\n<p>&nbsp;<\/p>\n<h3><span class=\"ez-toc-section\" id=\"what-is-division\"><\/span>What is Division?<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<p>When we say, &#8220;divide A by B&#8221;, &#8220;A&#8221; is the Numerator (Dividend), &#8220;B&#8221; is the Denominator (Divisor).<\/p>\n<p>The result is called the Quotient. \u00a0In integer division, the fractional portion is expressed as a Remainder, which represents the ratio of &#8220;what&#8217;s left over&#8221; to the denominator \/ divisor.<\/p>\n<ul>\n<li>Expressed as a formula:<br \/>\nN\/D = Q + R\/D<\/li>\n<li>N &#8211; Numerator, or Dividend, is the number being divided<\/li>\n<li>D &#8211; Denominator, or Divisor, is the size of the bucket used to slice up N.<\/li>\n<li>Q &#8211; Quotient (result), or the number of slices created if we carve up N in to D-sized buckets<\/li>\n<li>R &#8211; Remainder, or the quantity of N that&#8217;s left over, and won&#8217;t quite fill a whole D-sized bucket. \u00a0So the remainder is actually a fraction, a portion of 1, expressed as R\/D where R\/D &lt; 1<\/li>\n<li>Multiply the quotient \/ remainder by the denominator, to reconstruct N. \u00a0Remember that the remainder is a fraction, R\/D:<br \/>\nN\/D = Q + R\/D<br \/>\nMultiply by D:<br \/>\nN = Q * D + R<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<h3><span class=\"ez-toc-section\" id=\"finding-the-first-digit\"><\/span>Finding the First Digit<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<p>Let M be the magnitude in digits (minus 1) of the divisor, D.<\/p>\n<p>So if D = 6789, M would be 3 (4 digits, minus 1)<\/p>\n<p>A is the &#8220;quick divisor&#8221;, or the first digit of the divisor, with all other digits equal to zero. \u00a0Expressed as a formula:<\/p>\n<p style=\"padding-left: 30px;\">A = D &#8211; ( D MOD 10^M )<\/p>\n<p>In our example above:<\/p>\n<p style=\"padding-left: 30px;\">A = 6789 &#8211; ( 6789 MOD 10^3 )<\/p>\n<p style=\"padding-left: 30px;\">A = 6789 &#8211; ( 6789 MOD 1000 )<\/p>\n<p style=\"padding-left: 30px;\">A = 6789 &#8211; 789<\/p>\n<p style=\"padding-left: 30px;\">A = 6000<\/p>\n<p>We&#8217;re trying to set all digits to zero, except the first digit. \u00a0What&#8217;s the first thing you do in long division? \u00a0Drop all the zeros in the denominator. \u00a0So if we were trying to divide 567,892,345 by 6,789 \u00a0Reducing 6,789 to 6,000 allows us to reduce the precision of the numerator by the same number of digits. \u00a0We now have a single-digit math problem!<\/p>\n<p style=\"padding-left: 30px;\">567,892,345 \/ 6,789 \u00a0(Difficult)<\/p>\n<p style=\"padding-left: 30px;\">567,892,345 \/ 6,000 = 567,892 \/ 6 \u00a0(Easy)<\/p>\n<p>The &#8220;quick divisor&#8221;, A, will allow us to treat the entire division problem as single-digit division, easily computable by solving one digit at a time.<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<h2><span class=\"ez-toc-section\" id=\"process-overview\"><\/span>Process Overview<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>The process uses error-correcting iterative steps to converge on the quotient and remainder.<\/p>\n<p>Each iterative quotient candidate is multiplied by the divisor, and the difference between the result and the numerator is halved.<\/p>\n<p>This results in a new quotient candidate. \u00a0To more quickly converge, the previous two quotient candidates can be averaged.<\/p>\n<p>Once there is no further oscillation, and the absolute value of the remainder is less than the denominator (ratio of R\/D &lt;1) then the proper quotient has been determined.<\/p>\n<p>&nbsp;<\/p>\n<h2><span class=\"ez-toc-section\" id=\"algorithm-and-detailed-walkthrough\"><\/span>Algorithm and Detailed Walkthrough<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<h3><span class=\"ez-toc-section\" id=\"algorithm\"><\/span>Algorithm<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<p>Recap of variables:<\/p>\n<ul>\n<li>N &#8211; Numerator<\/li>\n<li>D &#8211; Denominator<\/li>\n<li>Q &#8211; Quotient<\/li>\n<li>R &#8211; Remainder<\/li>\n<li>M &#8211; Magnitude<\/li>\n<li>A &#8211; Quick Divisor<\/li>\n<\/ul>\n<p>Here is the algorithm (Assume all calculations are integer calculations):<\/p>\n<ul>\n<li>M = length in digits of D, minus 1. \u00a0So if D is 1234, there are 4 digits, M=3.<\/li>\n<li>A = D &#8211; (D MOD 10^M). \u00a0This results in the first digit of D, followed by all zeros<\/li>\n<li>Q = N \/ A<\/li>\n<li>R = D+1<\/li>\n<li>While \u00a0ABS(R)&gt;=D\n<ul>\n<li>R = N &#8211; (Q * D)<\/li>\n<li>Qn = Q + R \/ A<\/li>\n<li>Q = (Q + Qn) \/ 2<\/li>\n<\/ul>\n<\/li>\n<li>R = N &#8211; (Q * D) \u00a0 \u00a0Calculate a final value for R<\/li>\n<li>If R&lt;0 then\n<ul>\n<li>Q=Q-1<\/li>\n<li>R=R+D<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>Once the loop exits, Q is the quotient, R is the remainder.<\/p>\n<p>&nbsp;<\/p>\n<h3><span class=\"ez-toc-section\" id=\"walk-through-%e2%80%93-how-does-this-work\"><\/span>Walk Through &#8211; How does this work?<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<p>When you have to &#8220;guess&#8221; the quotient digit based on a multi-digit divisor, how do you do that? \u00a0Even the guess is an iterative process.<\/p>\n<p>Conversely, it&#8217;s easy to do a single-digit division. \u00a0Grab a pair of digits, divide, take the remainder times 10, grab the next digit, etc&#8230;<\/p>\n<p>So we start by creating a &#8220;quick divisor&#8221;, A, that can be calculated using single-digit division.<\/p>\n<p>The result is way off, but this is an iterative process.<\/p>\n<p>We start with an initial value for Q by using single-digit division to calculate N \/ A.<\/p>\n<p>&nbsp;<\/p>\n<h4><span class=\"ez-toc-section\" id=\"start-of-loop\"><\/span>Start of Loop<span class=\"ez-toc-section-end\"><\/span><\/h4>\n<p>The remainder, R, is the difference between our numerator N, and Q * D (our initial quotient candidate, times the denominator)<\/p>\n<p>By dividing R by A (the quick divisor), we can do another simple, single-digit division step, to get a value that can be added to Q, in order to make Q more accurate.<\/p>\n<p>Taking this approach results in oscillation. \u00a0To dampen the oscillation, we average Q and Qn:<\/p>\n<ul>\n<li>The original quotient candidate is Q.<\/li>\n<li>New Q, or Qn = Q (the original quotient candidate) + R \/ A \u00a0(the error or offset)<\/li>\n<li>Q = (Q + Qn) \/ 2 (average the two, to dampen oscillation, and reduce iterations by half)<\/li>\n<\/ul>\n<p>Once R settles in to a an absolute value &lt;=D, you have the right answer, Q<\/p>\n<p>A final computation step must be added, to calculate the final value for R based on the final value for Q, otherwise, you&#8217;d have the R corresponding to the old Q value.<\/p>\n<p>In some cases, R can stay negative, but converge to a an absolute value\u00a0\u00a0&lt;=D. \u00a0In this case, a final adjustment must be made:<\/p>\n<ul>\n<li>Subtract 1 from Q &#8211; forces Q * D to a value &lt;= N<\/li>\n<li>Add D to the remainder, R,\u00a0representing the &#8220;1&#8221; we subtracted from Q, and forcing R positive<\/li>\n<\/ul>\n<p>Q is now the proper quotient, and R is the remainder.<\/p>\n<p>&nbsp;<\/p>\n<h2><span class=\"ez-toc-section\" id=\"examples\"><\/span>Examples<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>&nbsp;<\/p>\n<h3><span class=\"ez-toc-section\" id=\"example-1\"><\/span>Example 1<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<p>Divide 999,999 by 7,777<\/p>\n<p>N (Numerator) = 999,999<\/p>\n<p>D (Denominator) = 7,777<\/p>\n<p>M = Len(D)-1, so M=3<\/p>\n<p>A = D &#8211; (D MOD 10^M)<\/p>\n<p style=\"padding-left: 30px;\">A = 7,777 &#8211; (7,777 MOD 1000)<\/p>\n<p style=\"padding-left: 30px;\">A = 7,777 &#8211; 777<\/p>\n<p style=\"padding-left: 30px;\">A = 7,000<\/p>\n<p>Q = N \/ A<\/p>\n<p style=\"padding-left: 30px;\">A = 999,999 \/ 7,000<\/p>\n<p style=\"padding-left: 30px;\">Q = 142 \u00a0 (remember, this is all integer math)<\/p>\n<p>R = D+1 = 7,778 (initial value, false condition for while loop)<\/p>\n<table border=\"0\" cellspacing=\"0\">\n<colgroup span=\"2\" width=\"85\"><\/colgroup>\n<colgroup width=\"97\"><\/colgroup>\n<colgroup span=\"5\" width=\"85\"><\/colgroup>\n<tbody>\n<tr>\n<td align=\"LEFT\" height=\"18\"><strong>Loop<\/strong><\/td>\n<td align=\"LEFT\"><strong>Old Q<\/strong><\/td>\n<td align=\"LEFT\"><strong>Old Q x D<\/strong><\/td>\n<td align=\"LEFT\"><strong>R<\/strong><\/td>\n<td align=\"LEFT\"><strong>R \/ A<\/strong><\/td>\n<td align=\"LEFT\"><strong>Qn<\/strong><\/td>\n<td align=\"LEFT\"><strong>Q<\/strong><\/td>\n<td align=\"LEFT\"><strong>Guess<\/strong><\/td>\n<\/tr>\n<tr>\n<td align=\"RIGHT\" height=\"17\">1<\/td>\n<td align=\"RIGHT\">142<\/td>\n<td align=\"RIGHT\">1,104,334<\/td>\n<td align=\"RIGHT\">-104,335<\/td>\n<td align=\"RIGHT\">-14<\/td>\n<td align=\"RIGHT\">128<\/td>\n<td align=\"RIGHT\">135<\/td>\n<td align=\"RIGHT\">945,560<\/td>\n<\/tr>\n<tr>\n<td align=\"RIGHT\" height=\"17\">2<\/td>\n<td align=\"RIGHT\">135<\/td>\n<td align=\"RIGHT\">1,049,895<\/td>\n<td align=\"RIGHT\">-49,896<\/td>\n<td align=\"RIGHT\">-7<\/td>\n<td align=\"RIGHT\">128<\/td>\n<td align=\"RIGHT\">131<\/td>\n<td align=\"RIGHT\">968,891<\/td>\n<\/tr>\n<tr>\n<td align=\"RIGHT\" height=\"17\">3<\/td>\n<td align=\"RIGHT\">131<\/td>\n<td align=\"RIGHT\">1,018,787<\/td>\n<td align=\"RIGHT\">-18,788<\/td>\n<td align=\"RIGHT\">-2<\/td>\n<td align=\"RIGHT\">129<\/td>\n<td align=\"RIGHT\">130<\/td>\n<td align=\"RIGHT\">992,222<\/td>\n<\/tr>\n<tr>\n<td align=\"RIGHT\" height=\"17\">4<\/td>\n<td align=\"RIGHT\">130<\/td>\n<td align=\"RIGHT\">1,011,010<\/td>\n<td align=\"RIGHT\">-11,011<\/td>\n<td align=\"RIGHT\">-1<\/td>\n<td align=\"RIGHT\">129<\/td>\n<td align=\"RIGHT\">129<\/td>\n<td align=\"RIGHT\">992,222<\/td>\n<\/tr>\n<tr>\n<td align=\"RIGHT\" height=\"17\">5<\/td>\n<td align=\"RIGHT\">129<\/td>\n<td align=\"RIGHT\">1,003,233<\/td>\n<td align=\"RIGHT\">-3,234<\/td>\n<td align=\"RIGHT\">0<\/td>\n<td align=\"RIGHT\">129<\/td>\n<td align=\"RIGHT\">129<\/td>\n<td align=\"RIGHT\">999,999<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>Compute the final value for R:<\/p>\n<p style=\"padding-left: 30px;\">R = N &#8211; ( Q * D )<\/p>\n<p style=\"padding-left: 30px;\">R = 999,999 &#8211; (129 * 7,777)<\/p>\n<p style=\"padding-left: 30px;\">R = -3,234<\/p>\n<p>Since R is negative, we have a final adjustment to Q and R<\/p>\n<p style=\"padding-left: 30px;\">Q = Q -1<\/p>\n<p style=\"padding-left: 30px;\">Q = 129-1<\/p>\n<p style=\"padding-left: 30px;\"><em><strong>Q = 128<\/strong><\/em><\/p>\n<p style=\"padding-left: 30px;\">R = R + D<\/p>\n<p style=\"padding-left: 30px;\">R = -3,234 + 7,777<\/p>\n<p style=\"padding-left: 30px;\"><em><strong>R = 4,543<\/strong><\/em><\/p>\n<p>Checking:<\/p>\n<p style=\"padding-left: 30px;\">N = Q * D + R<\/p>\n<p style=\"padding-left: 30px;\">999,999 = 128 * 7,777 + 4,543<\/p>\n<p style=\"padding-left: 30px;\">999,999 = 995,456 + 4,543<\/p>\n<p style=\"padding-left: 30px;\">999,999 = 999,999<\/p>\n<p style=\"padding-left: 30px;\">Check!<\/p>\n<p>&nbsp;<\/p>\n<h3><span class=\"ez-toc-section\" id=\"example-2\"><\/span>Example 2<span class=\"ez-toc-section-end\"><\/span><\/h3>\n<p>Divide 999,999,999 by\u00a0999,999<\/p>\n<p>N (Numerator) = 999,999,999<\/p>\n<p>D (Denominator) = 999,999<\/p>\n<p>M = Len(D)-1, so M=5<\/p>\n<p>A = D &#8211; (D MOD 10^M) = 900,000<\/p>\n<p>Q = N \/ A = 1,111<\/p>\n<p>R = D+1 = 1,000,000\u00a0(initial value, false condition for while loop)<\/p>\n<table border=\"0\" cellspacing=\"0\">\n<colgroup span=\"2\" width=\"85\"><\/colgroup>\n<colgroup width=\"97\"><\/colgroup>\n<colgroup span=\"5\" width=\"85\"><\/colgroup>\n<tbody>\n<tr>\n<td align=\"LEFT\" height=\"18\"><strong>Loop<\/strong><\/td>\n<td align=\"LEFT\"><strong>Old Q<\/strong><\/td>\n<td align=\"LEFT\"><strong>Q x D<\/strong><\/td>\n<td align=\"LEFT\"><strong>R<\/strong><\/td>\n<td align=\"LEFT\"><strong>R \/ A<\/strong><\/td>\n<td align=\"LEFT\"><strong>Qn<\/strong><\/td>\n<td align=\"LEFT\"><strong>Q<\/strong><\/td>\n<td align=\"LEFT\"><strong>Guess<\/strong><\/td>\n<\/tr>\n<tr>\n<td align=\"RIGHT\" height=\"17\">1<\/td>\n<td align=\"RIGHT\">1,111<\/td>\n<td align=\"RIGHT\">1,110,998,889<\/td>\n<td align=\"RIGHT\">-110,998,890<\/td>\n<td align=\"RIGHT\">-123<\/td>\n<td align=\"RIGHT\">988<\/td>\n<td align=\"RIGHT\">1,049<\/td>\n<td align=\"RIGHT\">938,000,061<\/td>\n<\/tr>\n<tr>\n<td align=\"RIGHT\" height=\"17\">2<\/td>\n<td align=\"RIGHT\">1,049<\/td>\n<td align=\"RIGHT\">1,048,998,951<\/td>\n<td align=\"RIGHT\">-48,998,952<\/td>\n<td align=\"RIGHT\">-54<\/td>\n<td align=\"RIGHT\">995<\/td>\n<td align=\"RIGHT\">1,022<\/td>\n<td align=\"RIGHT\">973,000,026<\/td>\n<\/tr>\n<tr>\n<td align=\"RIGHT\" height=\"17\">3<\/td>\n<td align=\"RIGHT\">1,022<\/td>\n<td align=\"RIGHT\">1,021,998,978<\/td>\n<td align=\"RIGHT\">-21,998,979<\/td>\n<td align=\"RIGHT\">-24<\/td>\n<td align=\"RIGHT\">998<\/td>\n<td align=\"RIGHT\">1,010<\/td>\n<td align=\"RIGHT\">988,000,011<\/td>\n<\/tr>\n<tr>\n<td align=\"RIGHT\" height=\"17\">4<\/td>\n<td align=\"RIGHT\">1,010<\/td>\n<td align=\"RIGHT\">1,009,998,990<\/td>\n<td align=\"RIGHT\">-9,998,991<\/td>\n<td align=\"RIGHT\">-11<\/td>\n<td align=\"RIGHT\">999<\/td>\n<td align=\"RIGHT\">1,004<\/td>\n<td align=\"RIGHT\">994,000,005<\/td>\n<\/tr>\n<tr>\n<td align=\"RIGHT\" height=\"17\">5<\/td>\n<td align=\"RIGHT\">1,004<\/td>\n<td align=\"RIGHT\">1,003,998,996<\/td>\n<td align=\"RIGHT\">-3,998,997<\/td>\n<td align=\"RIGHT\">-4<\/td>\n<td align=\"RIGHT\">1,000<\/td>\n<td align=\"RIGHT\">1,002<\/td>\n<td align=\"RIGHT\">998,000,001<\/td>\n<\/tr>\n<tr>\n<td align=\"RIGHT\" height=\"17\">6<\/td>\n<td align=\"RIGHT\">1,002<\/td>\n<td align=\"RIGHT\">1,001,998,998<\/td>\n<td align=\"RIGHT\">-1,998,999<\/td>\n<td align=\"RIGHT\">-2<\/td>\n<td align=\"RIGHT\">1,000<\/td>\n<td align=\"RIGHT\">1,001<\/td>\n<td align=\"RIGHT\">999,000,000<\/td>\n<\/tr>\n<tr>\n<td align=\"RIGHT\" height=\"17\">7<\/td>\n<td align=\"RIGHT\">1,001<\/td>\n<td align=\"RIGHT\">1,000,998,999<\/td>\n<td align=\"RIGHT\">-999,000<\/td>\n<td align=\"RIGHT\">-1<\/td>\n<td align=\"RIGHT\">1,000<\/td>\n<td align=\"RIGHT\">1,000<\/td>\n<td align=\"RIGHT\">999,000,000<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>Compute the final value for R:<\/p>\n<p style=\"padding-left: 30px;\">R = N &#8211; ( Q * D )<\/p>\n<p style=\"padding-left: 30px;\">R = 999,999,999 &#8211; (1,000 * 999,999)<\/p>\n<p style=\"padding-left: 30px;\">R = 999<\/p>\n<p>Since R\u00a0positive, we don&#8217;t need to adjust Q nor R<\/p>\n<p>Checking:<\/p>\n<p style=\"padding-left: 30px;\">N = Q * D + R<\/p>\n<p style=\"padding-left: 30px;\">999,999,999 = 1,000\u00a0*\u00a0999,999 + 999<\/p>\n<p style=\"padding-left: 30px;\">999,999,999 =\u00a0999,999,000 + 999<\/p>\n<p style=\"padding-left: 30px;\">999,999,999 = 999,999,999<\/p>\n<p style=\"padding-left: 30px;\">Check!<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<h2><span class=\"ez-toc-section\" id=\"corollary-in-base-x\"><\/span>Corollary in Base X<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>The nice thing about this algorithm is that it works in any base!<\/p>\n<p>The examples above are in base 10.<\/p>\n<p>Recalling our multiple-segment arbitrary-precision \u00a0data type, we used a string of Int16&#8217;s, of which each Int16 is used to store a 4-digit segment of some\u00a0very large number.<\/p>\n<p>If we consider each segment a base-10,000 digit, then we can perform the above algorithm one whole segment at a time instead of one digit at a time!<\/p>\n<p>In the above example, N = 999,999,999 and D = 999,999, these numbers would be represented by a string of Int16&#8217;s like this:<\/p>\n<ul>\n<li>N = 9:9999:9999 (3 segments)<\/li>\n<li>D = 99:9999 (2 segments)<\/li>\n<li>M = 1<\/li>\n<li>A = 99:9999 &#8211; ( 99:9999 MOD 10,000^M ) = 99:0000<\/li>\n<\/ul>\n<p>The first step would be to find the initial value of Q, by dividing N by A.<\/p>\n<p>This can be done one &#8220;digit&#8221; at a time:<\/p>\n<p style=\"padding-left: 30px;\">9:9999:9999 \/ 99:0000<\/p>\n<p style=\"padding-left: 30px;\">Fix up the precision based on A:<\/p>\n<p style=\"padding-left: 30px;\">9:9999 \/ 99<\/p>\n<p style=\"padding-left: 30px;\">Compare one digit at a time:<\/p>\n<p style=\"padding-left: 30px;\">9 \/ 99 = 0, \u00a0R 9<\/p>\n<p style=\"padding-left: 30px;\">The next segment multiplies the remainder times the base, adding the next digit:<\/p>\n<p style=\"padding-left: 30px;\">9 * 10,000 + 9999 = 99,999<\/p>\n<p>99,999 \/ 9 is easily computable using 32-bit math. \u00a0This results in an initial Q = 1,010<\/p>\n<p>Notice that we had to double our precision to accommodate carry \/ borrow. \u00a0This means that the segment data type\u00a0has to be able to accommodate n * b + n, where n is the largest number per segment, and b is the base.<\/p>\n<p>For example, since Int16 can accommodate any 4-digit number, it&#8217;s more expedient, if limited to 16-bit math, to limit the segment size to 2 digits. \u00a0This allows 99 * 100 + 99, or 9999 to be stored in a single segment, to allow for carry \/ borrow.<\/p>\n<p>On the other hand, if we continue to utilize 16-bit segments, we need a 32-bit data type to perform the segment-by-segment math.<\/p>\n<p>&nbsp;<\/p>\n<h2><span class=\"ez-toc-section\" id=\"summary\"><\/span>Summary<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>The algorithm outlined above can be used to perform arbitrary-precision division using character strings, or multi-segment strings of integers, and the concept works in any base.<\/p>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>I was working on a project that required simple arithmetic for very large integers, a set of algorithms called &#8220;Arbitrary Precision Math&#8221;. Thinking back to elementary school, simple algorithms exist for addition, subtraction, and multiplication of two numbers with any number of digits. To my surprise, every algorithm for division either relies on logarithms, which [&hellip;]<\/p>\n","protected":false},"author":16,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7,2],"tags":[],"class_list":["post-1632","post","type-post","status-publish","format-standard","hentry","category-analyses-and-responses","category-tech-support"],"_links":{"self":[{"href":"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-json\/wp\/v2\/posts\/1632","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-json\/wp\/v2\/users\/16"}],"replies":[{"embeddable":true,"href":"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-json\/wp\/v2\/comments?post=1632"}],"version-history":[{"count":10,"href":"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-json\/wp\/v2\/posts\/1632\/revisions"}],"predecessor-version":[{"id":2974,"href":"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-json\/wp\/v2\/posts\/1632\/revisions\/2974"}],"wp:attachment":[{"href":"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-json\/wp\/v2\/media?parent=1632"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-json\/wp\/v2\/categories?post=1632"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/justinparrtech.com\/JustinParr-Tech\/wp-json\/wp\/v2\/tags?post=1632"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}