-3
\$\begingroup\$

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 (<, >, ==, <=, >=, !=/<>)
  • 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 , so the lowest score wins!

\$\endgroup\$
  • \$\begingroup\$ What range do we need to support for d and (separately) n? \$\endgroup\$ – Neil Feb 15 '16 at 17:35
  • \$\begingroup\$ @Neil Any integers your language can support, including integers represented by floating point without loss of precision. For many languages this will be numbers up to 9007199254740991 (64-bit IEEE 754). \$\endgroup\$ – CJ Dennis Feb 15 '16 at 23:09
  • 1
    \$\begingroup\$ @ThomasKwa Solve this problem (mod) is a single operator in most languages, and often a single character (%). I'm attempting to replicate a method that a person can do in their head. The restrictions are because usually, no matter no carefully I explain what I am expecting, someone comes along and finds a loophole, which I find boring. As a consequence, I tend to go overboard trying to close loopholes before other people find them. \$\endgroup\$ – CJ Dennis Feb 16 '16 at 4:36
  • 1
    \$\begingroup\$ What if we use a non-mathematical algorithm? For example, reshaping a list into chunks of length n, then seeing how many are left over. You'll need to rule that out too. Again, this question is fundamentally about doing a problem a certain way, which takes the fun out of figuring out an algorithm. \$\endgroup\$ – lirtosiast Feb 16 '16 at 4:48
  • 1
    \$\begingroup\$ @CJDennis "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. " This isn't a good way to do things. Trying to find alternative methods to do things is a lot of the fun of code golfing. Do X without Y challenges tend not to work. \$\endgroup\$ – xnor Feb 16 '16 at 4:56
1
\$\begingroup\$

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;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.