Modulo code golf

Question

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

Answer 1

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

Answer 2

Perl, 62 bytes

Regex modulo

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

Answer 3

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;}

Answer 4

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.

Answer 5

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

Answer 6

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.

Answer 7

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.