Most people can't easily do modulus (or work out if a number is divisible by another number) in their heads because long division is harder than addition, subtraction and multiplication. The following method describes a way to calculate modulus in your head, as long as you can remember just a few different numbers. This challenge is to write some code that replicates this method instead of using the built-in modulo operator.
I apologise in advance for all of the restrictions, they are there to (hopefully) stop people from trying to work around the problem, instead of solving it the way it's presented. Another way of thinking about this is to assume that division is prohibitively expensive but the other three basic operators are relatively cheap to perform.
Decimal-multiplication modulo (d mod n) works by splitting the dividend (d) into chunks of the same length as the divisor (n), working from right to left. Then, working from left to right, each chunk is summed to a running total and the total is multiplied by a constant (c) before summing the next chunk. c is calculated by subtracting n from the next highest power of 10.
- You may use any method to calculate the lowest power of 10 that is greater than n, including logarithms
- You may keep subtracting n from c until c is less than n (but not negative)
- You must not use division or modulo to calculate c
- You must not convert any number to any base other than base 10
- You may use any method to split d into groups of decimal digits, including division and modulo if it makes your code easier
- You must only use the following mathematical operators on the chunks
- addition:
+,++ - subtraction:
-,--(not on numbers with more digits than n has) - multiplication:
*(only by c) - comparison (
<,>,==,<=,>=,!=/<>)
- addition:
- You must not use subtraction on any number with more digits than n, except when calculating c
- You must not subtract any value other than c, except when calculating c
- You must not multiply by any value other than c
- You must not use negative numbers at any point, including as the result of any calculation
You don't have to implement the method exactly as described here as long as you stick to its principles. E.g., if the divisor is 37 and one of the chunks is 56, you can subtract 37 from 56 to give 19 before using it further.
Your code will take two integers or string representations of decimal integers, whichever is most natural for your language. The first will be non-negative (d ≥ 0), the second will be positive (n ≥ 1). Your code will output a decimal integer or a string representation containing the result 0 ≤ d mod n ≤ n - 1.
Example
1234 mod 37
The lowest power of 10 higher than 37 is 100
c = 100 - 37 = 63 (26 is also acceptable as it is 63 - 37)
37 has two digits so split 1234 into two-digit chunks:
1234
% 37
====
12 34 -> vv
--
26 * 0 + 12 = 12
--
26 * 12 + 34 = 346
346 has more than two digits, repeat the process:
346
% 37
====
3 46 -> vv
--
26 * 0 + 3 = 3
--
26 * 3 + 46 = 124
124 also has more than two digits, repeat the process once more:
124
% 37
====
1 24 -> vv
--
26 * 0 + 1 = 1
--
26 * 1 + 24 = 50
Since 50 has two digits and is larger than 37, subtract 37 from it as many times as needed to bring the total below 37.
50
- 37
====
13
13 is indeed 1234 mod 37.
This is code-golf, so the lowest score wins!
1 Answer 1
ES7, 86 bytes
f=(d,n,t=10**(''+n).length)=>d<n?d:f(d<t?d-n:(g=d=>d<t?d:g((d-d%t)/t)*(t-n)+d%t)(d),n)
Ungolfed:
function modulo(d, n) {
var t = Math.pow(10, 1 + Math.floor(Math.log10(n)));
var c = t - n;
function chunk(p) {
if (p < t) return p; // reached the leftmost chunk
// first recursively process the left part of the number
return chunk(Math.floor(p / t)) * c + p % t;
}
while (d >= t) d = chunk(d);
while (d >= n) d -= n;
return d;
}
dand (separately)n? \$\endgroup\$