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\$
  • 1
    \$\begingroup\$ If division is disallowed, it WILL perform badly,because only repeated subtraction is left. \$\endgroup\$ – FUZxxl Feb 11 '11 at 21:14
  • 1
    \$\begingroup\$ Subtraction is not so bad but you also have multiplication. \$\endgroup\$ – Eelvex Feb 11 '11 at 21:26
  • 2
    \$\begingroup\$ Can the second operand be negative as well? \$\endgroup\$ – sepp2k Feb 11 '11 at 21:30
  • \$\begingroup\$ @sepp2k: It's not a requirement so treat it as it suits you. \$\endgroup\$ – Eelvex Feb 11 '11 at 21:33
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
| improve this answer | |
\$\endgroup\$
  • \$\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 '11 at 21:47
  • \$\begingroup\$ @Sepp2k: Now it works. \$\endgroup\$ – FUZxxl Feb 11 '11 at 22:26
  • 2
    \$\begingroup\$ Note that 0<1 is shorter than True \$\endgroup\$ – J B Feb 11 '11 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 '11 at 14:53
3
\$\begingroup\$

Perl, 62 bytes

Regex modulo

sub f{($a,$b)=@_;$_=1x$a;s/^(1{$b})+(1+)$/return length $2/e;}
| improve this answer | |
\$\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;}
| improve this answer | |
\$\endgroup\$
  • 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 '11 at 21:59
  • \$\begingroup\$ [:)] that was easy, thanks!.. I am so used to beautify the code oops! \$\endgroup\$ – Aman ZeeK Verma Feb 11 '11 at 22:06
  • \$\begingroup\$ I suggested an edit; discard it if you don't like it. \$\endgroup\$ – Eelvex Feb 11 '11 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\$ – Aman ZeeK Verma Feb 11 '11 at 22:32
  • \$\begingroup\$ It's 64 by removing the whitespace at the start \$\endgroup\$ – TuxCrafting Oct 1 '16 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.

| improve this answer | |
\$\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
| improve this answer | |
\$\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.

| improve this answer | |
\$\endgroup\$
  • \$\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 '11 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 '11 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 '11 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 '11 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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ This does not perform correctly for negative inputs. \$\endgroup\$ – Quelklef Oct 1 '16 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\$ – Erik the Outgolfer Oct 1 '16 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 '16 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\$ – Erik the Outgolfer Oct 1 '16 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.