1
\$\begingroup\$

The task is to build a numerical library for working with arbitrarily large integers that supports the following operations:

  • addition
  • subtraction
  • multiplication
  • division
  • modulo operation

However, the library must not use any primitive data types or arrays, neither directly nor indirectly (including booleans). For example, if you use Java, you can neither use AtomicInteger (because it uses bool internally) nor HashMap (because it uses arrays internally). You'll need to create your own data structures, without using any primitive data types, to represent numbers. (Inherited methods such as Java's hashCode don't count, as long as you don't use them in any way.) The only exception is local use of booleans in order to use conditionals (see the clarification points below).

There is only one exception: In order to make your library actually testable, provide two functions to convert from and to native integer representation. For example:

int toNative(MyNum n) { ... }
MyNum fromNative(int n) { ... }

This is the only part of your code that can use built-in data types, and it must not do anything except the conversion.

If in doubt, please ask.

Criteria: The code should be elegant, readable, concise (but no code-golf, readability is more important than code size), well documented, and if possible, asymptotically efficient (provide and justify your functions asymptotic time and space complexity). The most up-voted answer in 10 days wins.


Update: Since the puzzle seemed impossible to many people, let me give a hint:

public abstract class Nat {
    public static Nat fromInt(int n) {
        Nat r = new Zero();
        for(int i = 0; i < n; i++)
            r = new Succ(r);
        return r;
    }

    public static int toInt(Nat n) {
        int i = 0;
        for(Nat m = n; m instanceof Succ; m = ((Succ)m).n)
            i++;
        return i;
    }
}

final class Zero extends Nat {
}

final class Succ extends Nat {
    public final Nat n;

    public Succ(Nat n) {
        this.n = n;
    }
}

This allows to represent any natural number without primitive types, even though not very efficiently.

To further clarify:

  • Pointers are allowed to work with data structures as long as you use them only as opaque references. In particular, you may not use any pointer arithmetic.
  • NULL/nulls are allowed.
  • If the language of your choice requires it, you can use booleans (or a similar data type) for conditionals, but only locally in functions/methods, not as fields in your data structures, and you can't use anything beyond boolean operations. Bonus if you manage it without booleans (many languages are capable of that, such as those that use pattern matching).
  • Higher-level languages are better suited for the puzzle.
\$\endgroup\$
21
  • 12
    \$\begingroup\$ If we can't use primitive data types and we can't use complex data types because they use primitive types, what can we use? We obviously have to store data somehow. \$\endgroup\$
    – Josh
    Feb 3, 2014 at 21:10
  • 3
    \$\begingroup\$ I must be missing something obvious. Humour me... can you please show a (partial) example of how to "create your own data structures, without using any primitive data types"? \$\endgroup\$ Feb 3, 2014 at 22:42
  • 1
    \$\begingroup\$ Do you count pointers / references as primitive data types? The Wiki link you provide mentions them but I'm struggling to think of a way to produce a solution in most languages without them. \$\endgroup\$ Feb 3, 2014 at 23:52
  • 2
    \$\begingroup\$ Too bad it's closed, I had come up with something... A Terrible Secret! gist.github.com/anonymous/8794989 Unlimited precision even! \$\endgroup\$
    – Tobia
    Feb 4, 2014 at 0:01
  • 2
    \$\begingroup\$ Coming from a heavy c background the notion that pointers are excluded from "primitive data types" seems...dumb. And indeed the Wikipedia article you link specifically lists them as such. Likewise it lists both first class function and closures meaning that if we take that article as definitive then most of the suggested solutions are out. I can see what your trying to get at...Church style schemes and such, but this spec is a real mess. \$\endgroup\$ Feb 6, 2014 at 5:21

8 Answers 8

8
\$\begingroup\$

Haskell

Haskell is pretty good at defining obvious things from scratch.
Almost all definitions are simple translations of math axioms.
Doesn't support negative numbers, behaves badly on errors (e.g. 1-2 or 1/0).

data MyNum = Zero | S MyNum

toNative :: MyNum -> Integer
toNative Zero = 0
toNative (S n) = (toNative n) + 1
fromNative :: Integer -> MyNum
fromNative 0 = Zero
fromNative n = S $ fromNative $ n-1

-- numIfGE a b c = c if a>=b else 0
numIfGE _ Zero n = n
numIfGE Zero _ n = Zero
numIfGE (S a) (S b) n = numIfGE a b n

instance Num MyNum where
    a + Zero = a
    a + (S b) = S (a + b)

    a - Zero = a
    (S a) - (S b) = a - b

    a * Zero = Zero
    a * (S b) = a + (a*b)

a `divi` b = numIfGE a b (S $ (a - b) `divi` b)
a `modu` b = a - ((a `divi` b) * b)
\$\endgroup\$
6
\$\begingroup\$

Python 3

The code is a basic lambda calculus implementation I did some time ago when learning about calculus using an online resource which I cannot find anymore (can anybody give me a hint).

It works fine for positive numbers - extension to negatives should be possible.

# booleans and if
TRUE    = lambda x: lambda y: x
FALSE   = lambda x: lambda y: y
IF      = lambda x: x

# numerals
ZERO    = lambda f: lambda x: x
IS_ZERO = lambda n: n(lambda x: FALSE)(TRUE)

INC     = lambda n: lambda f: lambda x: f(n(f)(x))
DEC     = lambda n: lambda f: lambda x: n(lambda g: lambda h: h(g(f)))(lambda y: x)(lambda y: y)

# combinators
Y       = lambda f: (lambda x: f(x(x)))(lambda x: f(x(x)))
Z       = lambda f: (lambda x: f(lambda y: x(x)(y)))(lambda x: f(lambda y: x(x)(y)))

# arithmetic
ADD     = lambda m: lambda n: n(INC)(m)
SUB     = lambda m: lambda n: n(DEC)(m)
MUL     = lambda m: lambda n: n(ADD(n))(ZERO)

IS_LEQ  = lambda m: lambda n: IS_ZERO(SUB(m)(n))
MOD     = Z(lambda f: lambda m: lambda n: IF(IS_LEQ(n)(m))(lambda x: f(SUB(m)(n))(n)(x))(m))
DIV     = Z(lambda f: lambda m: lambda n: IF(IS_LEQ(n)(m))(lambda x: INC(f(SUB(m)(n))(n))(x))(ZERO))

# conversion function
def toNative(n) : return n(lambda x: x+1)(0)
def fromNative(n) : return ZERO if n==0 else INC(fromNative(n-1))

# Test code
n13 = fromNative(13)
n5 = fromNative(5)

print("13/5 = ",toNative(DIV(n13)(n5)))
print("13%5 = ",toNative(MOD(n13)(n5)))
\$\endgroup\$
3
\$\begingroup\$

Haskell

unlimited range, negative and positive values, no booleans except in native code

O(n) addition, subtraction (asymptotically optimal)
O(n^2) multiplication, division/modulo (no, I'm not going to implement the Karatsuba algorithm)

The representation is: a recursive type representing linked list of bits of the two's complement representation in the little endian order, terminated by either "all zeroes" or "all ones". Haskell has no trouble storing infinite lists in memory, but comparing their last elements is quite... hard.

show (producing a display form) runs backwards because prepending to a string is much faster than appending to it.

Addition, successor and predecessor are very simple. Carry is performed using the successor function. Note I didn't have to define subtraction. Haskell defines it for all Numbers as a - b = a + negate b).

Multiplication is the classical binary lattice multiplication, with the sum step being performed bottom-up.

Division is the classical binary long division (trial subtraction).

Haskell defines two sets of integer division operations. quotient/remainder round the quotient towards zero, while division/modulo round the quotient towards negative infinity. It defines divMod in terms of quotRem by subtracting one from the quotient (and the divisor from the modulus) if the sign of the remainder is opposite the sign of the divisor [source]. This is also the only place where the standard implementation uses native booleans internally (pattern matching probably does as well, but by the word of the author, this doeesn't count).

data LinkedInteger = Zero | MOne | And0 LinkedInteger | And1 LinkedInteger

toNative Zero = 0
toNative MOne = -1
toNative (And0 x) = 2 * toNative x
toNative (And1 x) = 2 * toNative x + 1

instance Show LinkedInteger where
   show = reverse.rshow
     where rshow  Zero    = "0.. "
           rshow  MOne    = "1.. "
           rshow (And0 x) = '0':(rshow x)
           rshow (And1 x) = '1':(rshow x)

fromNative   0  = Zero
fromNative (-1) = MOne
fromNative   x  | odd  x = And1 $ fromNative(x`div`2)
                | even x = And0 $ fromNative(x`div`2)

instance Enum LinkedInteger where 
    succ Zero    = And1 Zero
    succ MOne    = Zero
    succ(And0 x) = And1 x
    succ(And1 x) = And0(succ x)

    pred Zero    = MOne
    pred MOne    = And0 MOne
    pred(And0 x) = And1(pred x)
    pred(And1 x) = And0 x

    toEnum = fromNative
    fromEnum = toNative

instance Num LinkedInteger where 
    -- ensures sublinear performance in most cases
    Zero + x = x
    x + Zero = x
    MOne + x = pred x
    x + MOne = pred x
    And0 x + And0 y = And0 (x+y)
    And0 x + And1 y = And1 (x+y)
    And1 x + And0 y = And1 (x+y)
    And1 x + And1 y = And0 $ succ (x+y)

    negate  Zero    = Zero
    negate  MOne    = And1 Zero
    negate (And0 x) = And0 (negate x)
    negate (And1 x) = And1 $ pred (negate x)

    Zero   * y = Zero
    MOne   * y = -y
    And0 x * y =     And0 (x*y)
    And1 x * y = y + And0 (x*y)

    fromInteger = fromNative

    signum x = signum' (compare x Zero)
      where signum' LT = MOne
            signum' EQ = Zero
            signum' GT = And1 Zero

    abs x = ifNeg x (-x) x       


mappend EQ y = y
mappend x  _ = x

instance Eq LinkedInteger where x == y = (compare x y) == EQ

instance Ord LinkedInteger where
    compare Zero Zero = EQ
    compare MOne MOne = EQ
    compare MOne Zero = LT
    compare Zero MOne = GT
    compare (And0 x) (And0 y) = compare x y
    compare (And1 x) (And1 y) = compare x y
    compare (And0 x) (And1 y) = mappend (compare x y) LT
    compare (And1 x) (And0 y) = mappend (compare x y) GT
    compare Zero x = compare (And0 Zero) x
    compare MOne x = compare (And1 MOne) x
    compare x Zero = compare x (And0 Zero)
    compare x MOne = compare x (And1 MOne)

ifLt w x y z = ifNeg' (compare w x) y z
  where ifNeg' LT y _ = y
        ifNeg'  _ _ z = z

ifNeg x = ifLt x 0

half  Zero    = Zero
half  MOne    = MOne
half (And0 x) = x
half (And1 x) = x

andBitFrom  Zero    = And0
andBitFrom  MOne    = And1
andBitFrom (And0 x) = And0
andBitFrom (And1 x) = And1

instance Real LinkedInteger where toRational = toNative

instance Integral LinkedInteger where
  quotRem _ Zero = undefined
  quotRem x y = (ifNeg x
                  (ifNeg y
                    (let n (q,r) = ( q, -r) in n(quotRem'(-x)(-y)))
                    (let n (q,r) = (-q, -r) in n(quotRem'(-x)  y )))
                  (ifNeg y
                    (let n (q,r) = (-q,  r) in n(quotRem'  x (-y)))
                                                (quotRem'  x   y ) ))

    where quotRem' Zero _ = (Zero, Zero)
          quotRem'    x y = 
            let (qHalf, rHalf) = quotRem' (half x) y
                subdiv  = andBitFrom(x) rHalf
                subdiv' = subdiv - y
            in ifNeg subdiv' (And0 qHalf, subdiv) (And1 qHalf, subdiv')

  toInteger = toNative
\$\endgroup\$
2
\$\begingroup\$

perl

Here's my take, in perl. I thought this was a code-golfing post at first, so you may see some vestiges of that in the code. Anyway, I went to some effort to make the code as "tight" as possible, probably a little tighter than I otherwise would have. But I didn't go too far over the deep-end. Also note that I left in the prototypes on public functions (despite them being considered bad practice), because it made the test cases much less tedious to code up.

As for time and space, I left notation of the runtimes in the source at the heading of each subroutine, but I didn't take the time to prove them or anything, just to convince myself. Space is the more serious consideration of course - this implementation uses O(n) space to store an integer n, which is pretty bad. I wasn't sure exactly what I could get away with in terms of chars or encoding counts in inheritance patterns and such so I figured I'd do it the "canonical" (if slower) way. This has other effects too, for example, it takes O(n+m) time to ask if n equals m.

All that said, here's nat.pm, a complete (I believe) implementation in perl:

#!/usr/bin/perl

use strict;
use warnings;

package nat;

sub prev() { $_[0]->{prev}; }
sub next() { $_[0]->{next}; }

sub zero() { bless { prev => undef, next => undef } }

sub inc($) {
  bless defined $_[0]->next ?
        { prev => undef, next => $_[0]->next->next } :
        { prev => $_[0], next => undef }
}
sub dec($) {
  bless defined $_[0]->prev ?
        { prev => $_[0]->prev->prev, next => undef } :
        { prev => undef, next => $_[0] }
}

sub is_zero($)     { !defined $_[0]->prev && !defined $_[0]->next };
sub is_negative($) { defined $_[0]->next };
sub is_positive($) { defined $_[0]->prev };

sub from_native($) {
  my ($n) = @_;
  my $x = zero;
  $n--, $x = inc($x) while $n > 0;
  $n++, $x = dec($x) while $n < 0;
  return $x;
}
sub to_native($) {
  my ($x) = @_;
  my $n = 0;
  --$n, $x = $x->next while defined $x->next;
  ++$n, $x = $x->prev while defined $x->prev;
  return $n;
}

# returns 1 if x has greater magnitude than y
# returns -1 if x has lesser magnitude than y
# returns 0 if x and y have the same magnitude
sub _equal_depth { # O(x+y)
  my ($x, $y, $c) = @_;
  while( defined $x->{$c} ) {
    return 1 if !defined $y->{$c};
    $x = $x->{$c};
    $y = $y->{$c};
  }
  return defined $y->{$c} ? -1 : 0;
}

# x<y => -1, x>y => 1, x==y => 0
sub spaceship($$) { # O(x+y)
  my ($x, $y) = @_;
  if( is_positive( $x ) ) {
    return is_positive( $y ) ? _equal_depth($x, $y, 'prev') : 1;
  } elsif( is_negative( $x ) ) {
    return is_negative( $y ) ? _equal_depth($y, $x, 'next') : -1;
  } else {
    return is_zero( $y ) ? 0 : is_positive( $y ) ? -1 : 1;
  }
}

# the below are all O(x+y) as a result of spaceship()
#sub is_lt($$)  { my ($x, $y) = @_; return spaceship($x, $y) == -1 }
#sub is_gt($$)  { my ($x, $y) = @_; return spaceship($x, $y) == 1 }
#sub is_le($$)  { my ($x, $y) = @_; return spaceship($x, $y) != 1 }
#sub is_ge($$)  { my ($x, $y) = @_; return spaceship($x, $y) != -1 }
sub equals($$) { my ($x, $y) = @_; return spaceship($x, $y) == 0 }

sub clone($) { # O(x)
  my ($x) = @_;
  my $r = zero;
  if( is_positive($x) ) {
    $x = $x->prev, $r = inc($r)  while  defined $x->prev;
  } elsif( is_negative($x) ) {
    $x = $x->next, $r = dec($r)  while  defined $x->next;
  }
  return $r;
}

sub _add_sub { # O(x+y)
  my $is_sub = pop;
  my ($x, $y) = map { clone($_) } @_;
  while( 1 ) {
    if( is_positive( $y ) ) {
      $y = dec( $y );
      $x = $is_sub ? dec( $x ) : inc( $x );
    } elsif( is_negative( $y ) ) {
      $y = inc( $y );
      $x = $is_sub ? inc( $x ) : dec( $x );
    } else {
      last;
    }
  }
  return $x;
}

sub add($$) { # O(x+y)
  return _add_sub(@_, 0);
}

sub minus($$) { # O(x+y)
  return _add_sub(@_, 1);
}

sub negate($) {
  my ($x) = @_;
  return minus( zero, $x );
}

sub magnitude($) {
  my ($x) = @_;
  return is_negative($x) ? negate($x) : $x;
}

sub mult($$) { # O(x*y)
  my ($x, $y) = map { clone($_) } @_;
  my $r = zero;
  $x = negate($x), $y = negate($y)  if  is_negative($y);
  while( !is_zero( $y ) ) {
    $r = add($r, $x);
    $y = dec( $y );
  }
  return $r;
}

sub _div { # O(x*y)
  my $is_mod = pop;
  my ($x, $y) = map { clone($_) } @_;
  die "tried to divide by zero" if is_zero( $y );
  if($is_mod && (is_negative($x) || is_negative($y))) {
    if('nat.t' ne (caller(1))[1]) {
      warn "warning: modular arithmetic with negative operands not well defined!\n";
    }
  }
  my $is_neg = ( is_negative($x) xor is_negative($y) );
  $x = magnitude($x);
  $y = magnitude($y);
  # count up from zero by one until we get to $x
  # whenever we get to a multiple, increment the result by one and zero the remainder
  my $q = zero;
  my $r = zero;
  while( !is_zero( $x ) ) {
    $r = inc( $r );
    if( equals( $y, $r ) ) {
      $r = zero;
      $q = inc( $q );
    }
    $x = dec( $x );
  }
  $r = negate($r), $q = negate($q)  if  $is_neg;
  return $is_mod ? $r : $q;
}

sub divi($$) {
  return _div(@_, 0);
}
sub mod($$) {
  return _div(@_, 1);
}

# export
no strict 'refs';
*{scalar(caller)."::$_"} = \&$_ for grep { !/^[A-Z_]/ } keys %nat::;

1;

... and here is the test script I used when building it:

#!/usr/bin/perl

use strict;
use warnings;

use Test::More;

use nat;

my $x;

my $zero = zero;
ok( $zero );
ok( 0 == to_native $zero );
ok( is_zero $zero );
ok( !is_negative $zero );
ok( !is_positive $zero );

my $pos1 = inc $zero;
ok( $pos1 );
ok( 1 == to_native $pos1 );
ok( 0 == to_native dec $pos1 );
ok( !is_zero $pos1 );
ok( !is_negative $pos1 );
ok( is_positive $pos1 );

my $neg1 = dec $zero;
ok( $neg1 );
ok( -1 == to_native $neg1 );
ok(  0 == to_native inc $neg1 );
ok( !is_zero $neg1 );
ok( is_negative $neg1 );
ok( !is_positive $neg1 );

my $pos2 = inc $pos1;
ok( $pos2 );
ok( 2 == to_native $pos2 );
ok( 3 == to_native inc $pos2 );
ok( 1 == to_native dec $pos2 );
ok( !is_zero $pos2 );
ok( !is_negative $pos2 );
ok( is_positive $pos2 );

my $neg3 = dec dec $neg1;
ok( $neg3 );
ok( -3 == to_native $neg3 );
ok( -2 == to_native inc $neg3 );
ok( -4 == to_native dec $neg3 );
ok( !is_zero $neg3 );
ok( is_negative $neg3 );
ok( !is_positive $neg3 );

# make sure inc/dec can go "across" zero
ok(  1 == to_native inc inc inc dec dec zero );
ok( -1 == to_native dec dec dec inc inc zero );

ok( equals $zero, $zero );
ok( !equals $zero, $pos1 );
ok( !equals $zero, $neg1 );
ok( !equals $pos1, $neg1 );

ok( !equals $pos1, $pos2 );
ok( equals $pos1, $pos1 );
ok( equals $pos2, $pos2 );

ok( !equals $neg1, $neg3 );
ok( equals $neg1, $neg1 );
ok( equals $neg3, $neg3 );

ok(  0 == spaceship $neg3, $neg3 );
ok(  0 == spaceship $neg3, $neg3 );
ok( -1 == spaceship $neg3, $neg1 );
ok(  1 == spaceship $neg1, $neg3 );
ok( -1 == spaceship $neg3, $zero );
ok(  1 == spaceship $zero, $neg3 );
ok( -1 == spaceship $neg3, $pos1 );
ok(  1 == spaceship $pos1, $neg3 );
ok( -1 == spaceship $neg3, $pos2 );
ok(  1 == spaceship $pos2, $neg3 );

ok(  0 == spaceship $neg1, $neg1 );
ok(  0 == spaceship $neg1, $neg1 );
ok( -1 == spaceship $neg1, $zero );
ok(  1 == spaceship $zero, $neg1 );
ok( -1 == spaceship $neg1, $pos1 );
ok(  1 == spaceship $pos1, $neg1 );
ok( -1 == spaceship $neg1, $pos2 );
ok(  1 == spaceship $pos2, $neg1 );

ok(  0 == spaceship $zero, $zero );
ok(  0 == spaceship $zero, $zero );
ok( -1 == spaceship $zero, $pos1 );
ok(  1 == spaceship $pos1, $zero );
ok( -1 == spaceship $zero, $pos2 );
ok(  1 == spaceship $pos2, $zero );

ok(  0 == spaceship $pos1, $pos1 );
ok(  0 == spaceship $pos1, $pos1 );
ok( -1 == spaceship $pos1, $pos2 );
ok(  1 == spaceship $pos2, $pos1 );

ok(  0 == spaceship $pos2, $pos2 );
ok(  0 == spaceship $pos2, $pos2 );

#ok( is_lt $neg3, $neg1 );
#ok( !is_lt $neg3, $neg3 );
#ok( is_le $neg3, $neg1 );
#ok( is_le $neg1, $neg1 );
#ok( !is_gt $neg3, $neg1 );
#ok( !is_gt $neg3, $neg3 );
#ok( !is_ge $neg3, $neg1 );
#ok( is_ge $neg1, $neg1 );

ok( equals( inc inc inc inc inc inc zero, from_native 6 ) );
ok( equals( dec dec dec dec dec dec dec zero, from_native -7 ) );

$x = clone $pos2;
ok( equals $pos2, $x );
ok( 2 == to_native $x );
$x = clone $neg3;
ok( equals $neg3, $x );
ok( -3 == to_native $x );

ok( 2 == to_native add $zero, $pos2 );
ok( 1 == to_native add $zero, $pos1 );
ok( 1 == to_native add $pos1, $zero );
ok( 2 == to_native add $pos1, $pos1 );
ok( 3 == to_native add $pos1, $pos2 );
ok( 3 == to_native add $pos2, $pos1 );
ok( 4 == to_native add $pos2, $pos2 );

ok( -3 == to_native add $zero, $neg3 );
ok( -1 == to_native add $zero, $neg1 );
ok( -1 == to_native add $neg1, $zero );
ok( -2 == to_native add $neg1, $neg1 );
ok( -4 == to_native add $neg1, $neg3 );
ok( -4 == to_native add $neg3, $neg1 );
ok( -6 == to_native add $neg3, $neg3 );

ok( -2 == to_native add $neg3, $pos1 );
ok( -1 == to_native add $neg3, $pos2 );
ok(  0 == to_native add $neg1, $pos1 );
ok(  1 == to_native add $neg1, $pos2 );

ok( -2 == to_native minus $neg3, $neg1 );
ok(  2 == to_native minus $neg1, $neg3 );
ok( -3 == to_native minus $neg3, $zero );
ok(  3 == to_native minus $zero, $neg3 );
ok( -4 == to_native minus $neg3, $pos1 );
ok(  4 == to_native minus $pos1, $neg3 );
ok( -5 == to_native minus $neg3, $pos2 );
ok(  5 == to_native minus $pos2, $neg3 );

ok( -1 == to_native minus $neg1, $zero );
ok(  1 == to_native minus $zero, $neg1 );
ok( -2 == to_native minus $neg1, $pos1 );
ok(  2 == to_native minus $pos1, $neg1 );
ok( -3 == to_native minus $neg1, $pos2 );
ok(  3 == to_native minus $pos2, $neg1 );

ok( -1 == to_native minus $zero, $pos1 );
ok(  1 == to_native minus $pos1, $zero );
ok( -2 == to_native minus $zero, $pos2 );
ok(  2 == to_native minus $pos2, $zero );

ok( -1 == to_native minus $pos1, $pos2 );
ok(  1 == to_native minus $pos2, $pos1 );

ok( equals $pos1, negate($neg1) );
ok( equals $neg1, negate($pos1) );
ok(  3 == to_native negate $neg3 );
ok(  1 == to_native negate $neg1 );
ok(  0 == to_native negate $zero );
ok( -1 == to_native negate $pos1 );
ok( -2 == to_native negate $pos2 );

ok( equals magnitude($pos1), magnitude($neg1) );
ok( equals magnitude($neg1), magnitude($pos1) );
ok( equals magnitude($pos1), $pos1 );
ok( equals magnitude($neg1), $pos1 );
ok( 3 == to_native magnitude $neg3 );
ok( 1 == to_native magnitude $neg1 );
ok( 0 == to_native magnitude $zero );
ok( 1 == to_native magnitude $pos1 );
ok( 2 == to_native magnitude $pos2 );

ok(  3 == to_native mult $neg3, $neg1 );
ok(  0 == to_native mult $neg3, $zero );
ok( -3 == to_native mult $neg3, $pos1 );
ok( -6 == to_native mult $neg3, $pos2 );

ok(  1 == to_native mult $neg1, $neg1 );
ok(  0 == to_native mult $neg1, $zero );
ok( -1 == to_native mult $neg1, $pos1 );
ok( -2 == to_native mult $neg1, $pos2 );

ok(  0 == to_native mult $zero, $zero );
ok(  0 == to_native mult $zero, $pos1 );
ok(  0 == to_native mult $zero, $pos2 );

ok(  1 == to_native mult $pos1, $pos1 );
ok(  2 == to_native mult $pos1, $pos2 );

ok(  4 == to_native mult $pos2, $pos2 );

ok(  3 == to_native divi $neg3, $neg1 );
ok(  0 == to_native divi $neg1, $neg3 );
eval { to_native divi $neg3, $zero }; ok($@);
ok(  0 == to_native divi $zero, $neg3 );
ok( -3 == to_native divi $neg3, $pos1 );
ok(  0 == to_native divi $pos1, $neg3 );
ok( -1 == to_native divi $neg3, $pos2 );
ok(  0 == to_native divi $pos2, $neg3 );

eval { to_native divi $neg1, $zero }; ok($@);
ok(  0 == to_native divi $zero, $neg1 );
ok( -1 == to_native divi $neg1, $pos1 );
ok( -1 == to_native divi $pos1, $neg1 );
ok(  0 == to_native divi $neg1, $pos2 );
ok( -2 == to_native divi $pos2, $neg1 );

ok(  0 == to_native divi $zero, $pos1 );
eval { to_native divi $pos1, $zero }; ok($@);
ok(  0 == to_native divi $zero, $pos2 );
eval { to_native divi $pos2, $zero }; ok($@);

ok(  0 == to_native divi $pos1, $pos2 );
ok(  2 == to_native divi $pos2, $pos1 );

ok( 0 == to_native divi from_native(0), from_native(3) );
ok( 0 == to_native mod  from_native(0), from_native(3) );
ok( 0 == to_native divi from_native(1), from_native(3) );
ok( 1 == to_native mod  from_native(1), from_native(3) );
ok( 0 == to_native divi from_native(2), from_native(3) );
ok( 2 == to_native mod  from_native(2), from_native(3) );
ok( 1 == to_native divi from_native(3), from_native(3) );
ok( 0 == to_native mod  from_native(3), from_native(3) );
ok( 1 == to_native divi from_native(4), from_native(3) );
ok( 1 == to_native mod  from_native(4), from_native(3) );
ok( 1 == to_native divi from_native(5), from_native(3) );
ok( 2 == to_native mod  from_native(5), from_native(3) );
ok( 2 == to_native divi from_native(6), from_native(3) );
ok( 0 == to_native mod  from_native(6), from_native(3) );
ok( 2 == to_native divi from_native(7), from_native(3) );
ok( 1 == to_native mod  from_native(7), from_native(3) );

ok(  0 == to_native divi from_native(-1), from_native(3) );
ok( -1 == to_native mod  from_native(-1), from_native(3) );
ok(  0 == to_native divi from_native(-2), from_native(3) );
ok( -2 == to_native mod  from_native(-2), from_native(3) );
ok( -1 == to_native divi from_native(-3), from_native(3) );
ok(  0 == to_native mod  from_native(-3), from_native(3) );
ok( -1 == to_native divi from_native(-4), from_native(3) );
ok( -1 == to_native mod  from_native(-4), from_native(3) );

done_testing();
\$\endgroup\$
2
  • \$\begingroup\$ It depends on the tags of a question. If it has code-golf, then it's about the code size. If it has code-challenge then there is another criterion, and if it has popularity-contest, the most up-voted question wins (usually there are some less precise criteria given as well). \$\endgroup\$
    – Petr
    Feb 5, 2014 at 22:18
  • \$\begingroup\$ Ahh, thanks for the clarifiation, Petr! \$\endgroup\$ Feb 5, 2014 at 22:22
1
\$\begingroup\$

Go

Here's my partial submission in Go. Handles conversion to/from uint and sum to arbitrary precision.

The representation is binary, using a struct field (Unf) to store 1 bit of information (whether the pointer is nil or not) and another field (Chooie) to chain the next bit (more significant) which will chain another one if needed, and so on.

The performance is logarithmic with respect to the actual integers, just like in regular arbitrary precision libraries, except that the constant factors are hugely different.

package TerribleSecret

type Unf struct {
    Pak, Chooie *Unf
}

func FromNative(n uint) (u *Unf) {
    u = new(Unf)
    if n == 0 {
        return
    }
    if n&1 != 0 {
        u.Pak = u
    }
    u.Chooie = FromNative(n >> 1)
    return
}

func (u *Unf) ToNative() (n uint) {
    if u == nil {
        return
    }
    n = u.Chooie.ToNative()
    n <<= 1
    if u.Pak != nil {
        n |= 1
    }
    return
}

func (u *Unf) Add(n *Unf) {
    var f *Unf
    for {
        if u == nil {
            u = new(Unf)
        }
        if (n == nil || n.Pak == nil) != (f == nil) {
            if u.Pak != nil {
                u.Pak = nil
            } else {
                u.Pak = u
            }
        }
        if u.Pak != nil && (n == nil || n.Pak == nil) && f != nil {
            f = nil
        } else if u.Pak == nil && n != nil && n.Pak != nil && f == nil {
            f = n.Pak
        }
        if n != nil {
            n = n.Chooie
        }
        if n == nil && f == nil {
            break
        }
        if u.Chooie == nil {
            u.Chooie = new(Unf)
        }
        u = u.Chooie
    }
}

Unit tests

package TerribleSecret

import "testing"

func TestConversion(t *testing.T) {
    for n := uint(0); n < 10000; n++ {
        if r := FromNative(n).ToNative(); r != n {
            t.Fatalf("%d != %d", n, r)
        }
    }
}

func TestAdd(t *testing.T) {
    for x := uint(0); x < 1000; x++ {
        px := FromNative(x)
        for y := uint(0); y < 1000; y++ {
            py := FromNative(y)
            py.Add(px)
            if r := py.ToNative(); r != x+y {
                t.Fatalf("%d + %d = %d != %d", x, y, x+y, r)
            }
        }
    }
}
\$\endgroup\$
1
\$\begingroup\$

C#

Supports the 5 operations and negative values.

using System;

namespace NonPrimitive
{
    enum ComparisonResult
    {
        Greater, Equal, Less, Error
    }
    class MainClass
    {
        static void Main ()
        {
            Leaf l1 = Leaf.FromInt (10);
            Leaf l2 = Leaf.FromInt (-20);
            Leaf l3 = Leaf.FromInt (30);
            Leaf l4 = Leaf.FromInt (40);
            Leaf l5 = Leaf.FromInt (50);
            Leaf l6 = Leaf.FromInt (60);
            Leaf l7 = Leaf.FromInt (-20);
            Leaf l8 = Leaf.FromInt (80);
            Leaf l9 = Leaf.FromInt (20);
            Leaf l0 = Leaf.FromInt (50);
            Leaf a = l1.Add (l2);
            Leaf s = l4.Subtract (l3);
            Leaf m = l6.Multiply (l5);
            Leaf d = l8.Divide (l7);
            Leaf mo = l0.Modulo (l9);
            Console.WriteLine ("10 + -20: {0}", a.ToInt ());
            Console.WriteLine ("40 - 30: {0}", s.ToInt ());
            Console.WriteLine ("60 x 50: {0}", m.ToInt ());
            Console.WriteLine ("80 / -20: {0}", d.ToInt ());
            Console.WriteLine ("50 % 20: {0}", mo.ToInt ());
        }
    }
    class Leaf
    {
        public Leaf Parent;
        public Leaf Child;
        public Leaf Negative;
        public Leaf (Leaf parent)
        {
            Parent = parent;
        }
        public Leaf ReverseSign()
        {
            Leaf k = this.GetGrandParent ();
            if(k.Negative != null)
                k.Negative = null;
            else
                k.Negative = new Leaf(null);
            return k;
        }
        public Leaf CreateNewLeaf()
        {
            Child = new Leaf(this);
            return Child;
        }
        public Leaf AttachLeaf(Leaf leaf)
        {
            Child = leaf;
            Child.Parent = this;
            return this;
        }
        public Leaf RemoveChild()
        {
            this.Child = null;
            return this;
        }
        public Leaf GetGrandChild ()
        {
            Leaf k = this;
            while(k.Child != null)
                k = k.Child;
            return k;
        }
        public Leaf Add (Leaf a)
        {
            Leaf t = this.GetGrandChild ().AttachLeaf (a.GetGrandParent ()).GetGrandChild ().Parent.RemoveChild ().GetGrandParent ();
            if ((a.Negative == null && this.Negative == null) ||
                (a.Negative != null && this.Negative != null))
                return t.GetGrandParent ();
            return t.GetGrandParent ().ReverseSign ();
        }
        public Leaf GetGrandParent ()
        {
            Leaf k = this;
            while(k.Parent != null)
                k = k.Parent;
            return k;
        }
        public Leaf Multiply (Leaf t)
        {
            Leaf ret = new Leaf(null);
            bool sign = (t.Negative == null && this.Negative == null) ||
                        (t.Negative != null && this.Negative != null);
            t = t.GetGrandParent ();
            Leaf temp = this;
            while (t.Child != null) {
                while(true)
                {
                    if(temp.Child == null)
                        break;
                    ret = ret.CreateNewLeaf ();
                    temp = temp.Child;
                }
                temp = this.GetGrandParent ();
                t = t.Child;
            }
            if(!sign)
                return ret.GetGrandParent ().ReverseSign ();
            return ret.GetGrandParent ();
        }
        public Leaf Divide (Leaf t)
        {
            Leaf temp = this.GetGrandParent ();
            bool sign = (t.Negative == null && this.Negative == null) ||
                        (t.Negative != null && this.Negative != null);
            Leaf ret = new Leaf (null);
            while (temp.Compare (t) == ComparisonResult.Greater || temp.Compare (t) == ComparisonResult.Equal) {
                temp = temp.Subtract (t);
                ret = ret.CreateNewLeaf ();
            }
            if(!sign)
                return ret.GetGrandParent ().ReverseSign ();
            return ret.GetGrandParent ();
        }
        public ComparisonResult Compare (Leaf a)
        {
            Leaf t = this.GetGrandParent ();
            a = a.GetGrandParent ();
            while (true) {
                if(t.Child == null && a.Child != null)
                    return ComparisonResult.Less;
                if(t.Child == null && a.Child == null)
                    return ComparisonResult.Equal;
                if(t.Child != null && a.Child == null)
                    return ComparisonResult.Greater;
                t = t.Child;
                a = a.Child;
            }
        }
        public Leaf Modulo(Leaf t)
        {
            Leaf temp = this.GetGrandParent ();
            bool sign = (t.Negative == null && this.Negative == null) ||
                        (t.Negative != null && this.Negative != null);
            while (temp.Compare (t) == ComparisonResult.Greater || temp.Compare (t) == ComparisonResult.Equal) {
                temp = temp.Subtract (t);
            }
            if(!sign)
                return temp.GetGrandParent ().ReverseSign ();
            return temp.GetGrandParent ();
        }
        public Leaf Subtract (Leaf a)
        {
            Leaf temp = this.GetGrandParent();
            a = a.GetGrandParent ();
            Leaf counter = new Leaf (null);
            while (true) {
                if(a.Child != null && temp.Child != null) {
                    temp = temp.Child;
                    a = a.Child;
                } else if (a.Child != null && temp.Child == null) {
                    a = a.Child;
                    counter = counter.CreateNewLeaf ();
                } else if (temp.Child != null && a.Child == null) {
                    temp = temp.Child;
                    counter = counter.CreateNewLeaf ();
                }
                else if(temp.Child == null && a.Child == null) {
                    break;
                }
            }
            a = a.GetGrandParent ();
            if(this.Compare (a) == ComparisonResult.Less)
                return counter.ReverseSign ();
            else
                return counter.GetGrandParent ();
        }
        public int ToInt()
        {
            Leaf temp = this.GetGrandParent ();
            int ret = 0;
            while(true)
            {
                if(temp.Child != null) {
                    ret++;
                    temp = temp.Child;
                    continue;
                }
                break;
            }
            if(this.Negative != null)
                return -ret;
            return ret;
        }
        public static Leaf FromInt (int a)
        {
            Leaf ret = new Leaf (null);
            bool neg = a < 0;
            if (neg)
                a = Math.Abs (a);
            for (int i = 0; i < a; i++) {
                ret = ret.CreateNewLeaf ();
            }
            while (true) {
                if(ret.Parent != null)
                    ret = ret.Parent;
                else
                    break;
            }
            if(neg)
                return ret.ReverseSign ();
            return ret;
        }
    }
}

Also, the class is named "Leaf" because it uses a tree-like structure.

\$\endgroup\$
0
\$\begingroup\$

Brainfuck (incomplete)

Adding?

,>,[-<+>]

Subtracting?

,>,[-<->]
\$\endgroup\$
8
  • \$\begingroup\$ I admire the attempt to answer what could be a poorly specified or impossible question! But you seem to be operating on an array of bytes (as you must in Brainfuck), so isn't that violating the terms of the problem? (i.e. using both arrays and a primitive data type?) Anyways, kudos for posting something while the rest of us debate in the comments! \$\endgroup\$ Feb 4, 2014 at 2:28
  • \$\begingroup\$ @DarrenStone Thanks :) I definitely think the other questions do it better though. \$\endgroup\$
    – Timtech
    Feb 4, 2014 at 11:37
  • \$\begingroup\$ @darren-stone technically all computers have one really large array of bytes, but I disagree that BF does since random access is impossible. I've created a lot of data structures in BF and you need to simulate random access array through bread crumbs and loops just as you can simulate an array with linked lists in other languages. (imagine you read a byte and need to use the input as index in your array) \$\endgroup\$
    – Sylwester
    Feb 4, 2014 at 19:22
  • \$\begingroup\$ How do you feel about the primitive data type restriction? BF has an 8-bit byte as a primitive data type. Operating with - and + on bytes may or may not be in the spirit of the question. These are just my thoughts -- it's a popularity contest in the end, so the mob will decide an answer's validity. I like BF. I love Forth even more and I was considering a Forth-based submission, but I'm unclear in a stack model how I could push or pop or operate on a number and still be compliant. \$\endgroup\$ Feb 4, 2014 at 20:20
  • 1
    \$\begingroup\$ @Sylwester String ;} \$\endgroup\$
    – Timtech
    Feb 4, 2014 at 23:51
0
\$\begingroup\$

C++ lambda functions

#include <cstdio>
#include <functional>

using std::function;

typedef function<int(int, function<int(int)>)> church;

church zero = [](int x, function<int(int)> f){ return x; };
function<church(church)> successor = [](church n)
{
  return [=](int x, function<int(int)> f)
  {
    return n(f(x),f);
  };
};

function<church(church, church)> plus = [](church n, church m)
{
  return [=](int x, function<int(int)> f)
  {
    return n(m(x, f), f);
  };
};

function<church(church, church)> times = [](church n, church m)
{
  return [=](int x, function<int(int)> f)
  {
    return m(x, [=](int y){ return n(y, f); });
  };
};

int main()
{
  function<int(int)> convert = [](int x){
    return x + 1;
  };
  auto resf0 = successor(successor(zero));
  int res0 = resf0(0, convert);
  printf("%i\n", res0); // 2

  auto resf1 = successor(resf0);
  int res1 = resf1(0, convert);
  printf("%i\n", res1); // 3

  auto resf2 = plus(resf0, resf1);
  int res2 = resf2(0, convert);
  printf("%i\n", res2); // 5

  auto resf3 = times(resf1, resf2);
  int res3 = resf3(0, convert);
  printf("%i\n", res3); // 15
}

This may not strictly follow the rules, but I wrote this, and somebody else revised it to this in August 2013. Ints are only used as a placeholder datatype, and also so that we can convert the weird function types to actual numbers.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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