CODEWITHSUNDEEP
ocaml
John
John

Reputation: 29

Add numbers in base 10.000 with ocaml

I try to add numbers represented by a list, for example:

0 = []
1 = [1]
2005 = [2005]
123456 = [3456; 12]
1234567890 = [7890; 3456; 12]
1000000001 = [1; 0; 10]

so add [9999] [1] = [0;1]

I've done this:

let rec add l1 l2 =
match l1, l2 with
| n::l1', m::l2' -> if n+m < 10000 then
                        (n+m)::(add l1' l2')
                    else
                        begin
                            match l1', l2' with
                            | p::l1'', q::l2'' -> ((n+m) - 10000)::(add ((1+p)::l1'') l2')
                            | p::l1'', [] -> ((n+m) - 10000)::(add ((1+p)::l1'') l2')
                            | [], q::l2'' -> ((n+m) - 10000)::(add l1' ((1+q)::l2''))
                            | [], [] -> ((n+m) - 10000)::[1]
                        end
| [], [] -> []
| m::l1', [] -> m::(add l1' [])                    
| [], m::l2' -> m::(add [] l2')

but it doesn't work with something like add [9999;9999] [1] which gives [0; 10000] instead of [0;0;1].

There is a problem with the carry, but I can't find it.

It works with add [8500;6000] [5600;452].

Upvotes: 2

Views: 153

Answers (3)

didierc
didierc

Reputation: 14750

Let's have a look at the issue in your code. I have put my explanations of the problem in the comments:

let rec add l1 l2 =
   match l1, l2 with
   | n::l1', m::l2' -> if n+m < 10000 then
                       (n+m)::(add l1' l2')
                       else
                       begin
                         (* in all these cases you don't check if 1+p is > base *) 
                         match l1', l2' with
                          | p::l1'', q::l2'' -> ((n+m) - 10000)::(add ((1+p)::l1'') l2')
                          | p::l1'', [] -> ((n+m) - 10000)::(add ((1+p)::l1'') l2')
                          | [], q::l2'' -> ((n+m) - 10000)::(add l1' ((1+q)::l2''))
                          | [], [] -> ((n+m) - 10000)::[1]
                       end
   | [], [] -> []
   (* and the error above causes problem in these arms, since m can now be > base *)
   | m::l1', [] -> m::(add l1' [])
   | [], m::l2' -> m::(add [] l2')

Let's put the special cases first, replace the literal constant with a value, remve superfluous parentheses and fix the carry mistake.

let rec add l1 l2 base =
   match l1, l2 with
   | [], [] -> []
   | m::l1', []
   | [], m::l1' -> if m >= base then m-base::add l1' [1] base else m::l1'
   | n::l1', m::l2' -> let r = n + m in 
                       if r < base then
                         r::add l1' l2' base
                       else begin
                         match l1', l2' with
                          | [], []      -> [r-base ; 1]
                          | p::l1'', []
                          | [], p::l1'' -> r-base::add [] (1+q::l1'') base
                          | p::l1'', _  -> r-base::add (1+p::l1'') l2' base
                       end

Now we can see that a bit of code could be extracted and turned into a dedicated function:

let rec add l1 l2 base =
   let rec carry = function 
    | [] -> []
    | [x] when x >= base -> [x-base;1]
    | x::y::l when x >= base -> x-base::carry (y+1::l)
    | l -> l
   in
   match l1, l2 with
   | [], [] -> []
   | l1, []
   | [], l1 -> carry l1
   | n::l1', m::l2' -> let r = n + m in
                       if r < base then
                         r::add l1' l2' base
                       else begin
                         match l1', l2' with
                          | [], []     -> [r-base ; 1]
                          | l1'', []
                          | []  , l1'' -> carry (r::l1'')
                          | p::l1'', _ -> r-base::add (1+p::l1'') l2' base
                       end

Now your code should work with the carry preserved, and as a bonus be able to work with any natural base.

Upvotes: 0

Andreas Rossberg
Andreas Rossberg

Reputation: 36118

The problem is with your denormalized representation, which can temporarily create digits larger than 9999, which you don't expect in all places. Here is a simple solution with explicit carry that avoids that issue:

let base = 10_000
let rec add' xs ys c =
  match xs, ys with
  | [], [] -> if c = 0 then [] else [c]
  | [], zs | zs, [] -> add' [0] zs c
  | x::xs', y::ys' -> (x + y + c) mod base :: add' xs' ys' ((x + y + c) / base)
let add xs ys = add' xs ys 0

Upvotes: 2

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66823

It looks to me like your cases assume that digits are always less than or equal to 9999, but this isn't true when there is a carry. So you need to check against 10000 even when one of the lists is empty.

Upvotes: 4

Related Questions