5
\$\begingroup\$

Write a function f(a,b) that returns a mod b given the constraints:

  • you can't use division in any way
  • f(a,b) is always positive, eg: f(-1,5) = 4
  • it performs reasonably well for values of ~10e50 for a and b
\$\endgroup\$
4
  • 1
    \$\begingroup\$ If division is disallowed, it WILL perform badly,because only repeated subtraction is left. \$\endgroup\$
    – FUZxxl
    Feb 11, 2011 at 21:14
  • 1
    \$\begingroup\$ Subtraction is not so bad but you also have multiplication. \$\endgroup\$
    – Eelvex
    Feb 11, 2011 at 21:26
  • 2
    \$\begingroup\$ Can the second operand be negative as well? \$\endgroup\$
    – sepp2k
    Feb 11, 2011 at 21:30
  • \$\begingroup\$ @sepp2k: It's not a requirement so treat it as it suits you. \$\endgroup\$
    – Eelvex
    Feb 11, 2011 at 21:33

7 Answers 7

6
\$\begingroup\$

Haskell 36 35 (34? 33)

If I may call the function ? instead:

1234567890123456789012345678901234
a?b|a<0=(a+b)?b|a>b=(a-b)?b|0<1=a

Elseway:

f a b|a<0=f(a+b)b|a>b=f(a-b)b|0<1=a
\$\endgroup\$
4
  • \$\begingroup\$ Nice idea, but this does not meet the requirements as it does not work at all if a is negative (it will just return a unchanged). \$\endgroup\$
    – sepp2k
    Feb 11, 2011 at 21:47
  • \$\begingroup\$ @Sepp2k: Now it works. \$\endgroup\$
    – FUZxxl
    Feb 11, 2011 at 22:26
  • 2
    \$\begingroup\$ Note that 0<1 is shorter than True \$\endgroup\$
    – J B
    Feb 11, 2011 at 23:13
  • 1
    \$\begingroup\$ Could you try running this with input 10^50, 3? I'm pretty sure it wouldn't complete. \$\endgroup\$
    – Dogbert
    Feb 12, 2011 at 14:53
3
\$\begingroup\$

Perl, 62 bytes

Regex modulo

sub f{($a,$b)=@_;$_=1x$a;s/^(1{$b})+(1+)$/return length $2/e;}
\$\endgroup\$
2
\$\begingroup\$

Java Solution, 114 66 chars

Its now 66, thanks sepp2k!~

 int m(int x,int y){x=(x<0)?-(x*y-x):x;while(x>=y) x-=y;return x;}
\$\endgroup\$
7
  • 1
    \$\begingroup\$ This is 80 character if you remove the unnecessary whitespace. 73 if you also make the method non-static. 66 if you additionally make it package-private. \$\endgroup\$
    – sepp2k
    Feb 11, 2011 at 21:59
  • \$\begingroup\$ [:)] that was easy, thanks!.. I am so used to beautify the code oops! \$\endgroup\$ Feb 11, 2011 at 22:06
  • \$\begingroup\$ I suggested an edit; discard it if you don't like it. \$\endgroup\$
    – Eelvex
    Feb 11, 2011 at 22:24
  • \$\begingroup\$ I dont know, If this is right place to ask this or not.. but I do not know how to strike off (that must be easy.. idiot aman :P ) \$\endgroup\$ Feb 11, 2011 at 22:32
  • \$\begingroup\$ It's 64 by removing the whitespace at the start \$\endgroup\$ Oct 1, 2016 at 18:08
2
\$\begingroup\$

Haskell (22)

Abuse of the rules, please don't downvote: Mathematically, the modulus may be arbitrary large, because all moduli are equivalent. Thus, you may also use this, it WILL always return a positive result:

1234567890123456789012
a?b|a<0=(a+b)?b|True=a

And it will also always satisfy the equation

a?b = c <-> n*b + c = a

For some integer n.

\$\endgroup\$
2
\$\begingroup\$

Ruby - 72 chars

f=->a,b{a==b&&0||a<b&&a+(a<0&&b||0)||(t=b;t<<=1until t>a;f[a-(t>>1),b])}

Uses recursion like a Binary Search to find the remainder.

Test

p f[106, 95]
p f[23, 2]
p f[-1, 5]
p f[20, 7]
p f[10**100, 3]
p f[4*10**200, 3123123]

11
1
4
6
1
823660
\$\endgroup\$
2
\$\begingroup\$

Brainfuck - 37 characters

,>,<[->-[>+>>]>[+[-<+>]>+>>]<<<<<]>>.

Takes a and b as bytes from standard input. Outputs one byte. Does not meet criteria to work with arbitrary size numbers, but to do so in brainfuck would not be simple.

\$\endgroup\$
4
  • \$\begingroup\$ I'm torn. The problem doesn't explicitely ask for arbitrary size integers, which would be a pain to implement in BF, that's for sure. But you're not even close to performing "well" for e50, since you won't perform it at all. \$\endgroup\$
    – J B
    Dec 15, 2011 at 23:58
  • \$\begingroup\$ The more I think about it, the more I think this is defensible. All you need to make it handle e50 is an implementation that works on arbitrarily large numbers. Those do exist. Then it is just a matter of defining efficiency. Since this performs a whole lot better than brainfuck's built in modulo operator, I say it passes that too. \$\endgroup\$
    – captncraig
    Dec 16, 2011 at 15:01
  • \$\begingroup\$ I have no issue with the efficiency. What got me started is that no BF implementation I know of would be able to run your code on anything close to e50. The easy hurdle is the cell size, but implementations do exist that implement these as bignums. The hard one is input. I don't know of a single implementation that returns anything over 255, and can't conceive a reasonable one returning anything over 2^32. You could always find one and read input over several operations, but your character count doesn't reflect that. (publishing a new implementation for the the task is frowned upon) \$\endgroup\$
    – J B
    Dec 16, 2011 at 16:13
  • \$\begingroup\$ Fair enough. I was assuming I had an implementation that allows an arbitrarily large bignum input. Failing to find (or be allowed to create) that, this submission probably does not meet the requirements. It definitely can't handle negative input anyways. But it is remarkably competitive in count for a BF program, even if it is not quite there. \$\endgroup\$
    – captncraig
    Dec 16, 2011 at 16:44
1
\$\begingroup\$

Python 2, 35 bytes

f=lambda a,b:a if a<b else f(a-b,b)

Sadly, I can't use and/or short-circuiting here, so I have to do with one more byte.

\$\endgroup\$
4
  • \$\begingroup\$ This does not perform correctly for negative inputs. \$\endgroup\$
    – Quelklef
    Oct 1, 2016 at 18:05
  • \$\begingroup\$ @Quelklef It doesn't have to. It would have been nice to include negatives as well, since this is ½ trivial as of now, though. \$\endgroup\$ Oct 1, 2016 at 18:08
  • \$\begingroup\$ I think I'm reading this differently than you. Either way, I guess you're right, since there's already an accepted answer \$\endgroup\$
    – Quelklef
    Oct 1, 2016 at 18:14
  • \$\begingroup\$ @Quelklef I read that comment as "you can treat negatives any way", which means that undefined behavior can occur as well. \$\endgroup\$ Oct 1, 2016 at 18:16

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.