CODEWITHSUNDEEP
functional-programmingocaml
Luke
Luke

Reputation: 553

Subtraction in Ocaml, I can't quite nail down this bug

let rec sub' list1 list2 carry = match (list1, list2, carry) with
    | list1, [], 0       -> list1
    | [], list2, 0       -> list2
    | list1, [], carry   -> sub' list1 [carry] 0
    | [], list2, carry   -> sub' [carry] list2 0
    | car1::cdr1, car2::cdr2, carry ->
      let minus = car1 - car2 + carry



       in  minus mod radix :: sub' cdr1 cdr2 (minus / radix)

radix is set to 10

So, this is the code I have to subtract two numbers (list1 and list2). This is based on given code that I modified, so I'm not entirety sure how it works. It does work however, for most things. 5 - 4 = 1 10 - 20 = -10 etc.

But, it has this weird bug for larger numbers, 100 - 50 = "1-50" which is closeish, it has the "50" we want, but with some extra junk.

I've been trying to figure this out for a while, and I'm rather stuck.

Edit:

let length    = List.length
let car       = List.hd
let cdr       = List.tl
let map       = List.map
let reverse   = List.rev
let strcat    = String.concat
let strlen    = String.length
let strsub    = String.sub
let zero      = Bigint (Pos, [])



let rec zeros' rev = 
if (car rev) = 0 then
  lead_zeros' (cdr rev)
else (reverse rev)

let zeros list = match list with
| [0] -> list
| [] -> []
| list -> let reversed = reverse list
          in lead_zeros' reversed

Upvotes: 0

Views: 473

Answers (1)

kne
kne

Reputation: 1418

I did not analyze your code completely, but I believe the problem is that division rounds to zero, while you would need it to round down. For example, (-3) / 5 = 0 and (-3) mod 5 = -3 while you would need (-3) / 5 = -1 and (-3) mod 5 = 2.

It seems an invariant is minus >= -radix, so a simple fix would be to add radix to minus and adjust all else accordingly:

let minus = car1 - car2 + carry + radix
  in  minus mod radix :: sub' cdr1 cdr2 (minus / radix - 1)

This shifts the division and modulo into the nonnegative range, where it works as expected.

Upvotes: 1

Related Questions