CODEWITHSUNDEEP
ocaml
user1008820
user1008820

Reputation: 181

How to implement multiplication by an integer with a big integer in ocaml without library functions?

I'm currently trying to implement multiplication by an integer with a big integer in Ocaml without library functions.

Here is what I have so far:

let rec mulByDigit i l = 
  match l with
    [] -> []
  | h::t -> 
      match t with
        [] -> [(h*i) mod 10]
      | x::y -> 
          match y with
            [] -> [x*i/10+(h*i) mod 10]@mulByDigit i t
          | a::b -> [(x*i/10+(h*i)mod 10+(a*i/10+(x*i) 
                             mod 10)/10) mod 10]@mulByDigit i t

which for i = 9 and l = [9;9;9;9] gives me [9;9;9;1] when what is desired is [8;9;9;9;1]

As I understand it, the algorithm for this is to take information from the last digit*i, current digit*i and the next digit*i to construct the current digit for the answer list. However there are 2 cases where this isn't true. For the first digit and the last digit of the answer list, the last digit takes info from the current digit*i and the preceding digit*i of the input list and the first digit takes info from current digit*i and the succeeding digit*i of the input list. I can take care of the last digit's special case because of pattern matching with [] at the very end but I can't figure out how to do the special case for the first digit since I don't see any conditions I can put in an if then statement to only occur on the initial call of this function.

Any help would be appreciated.

Upvotes: 2

Views: 2013

Answers (2)

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66823

Well, this also sounds kinda like a homework problem. Here are a couple of observations.

You might get prettier looking code if you represent your numbers with the units digit at the head of the list rather than at the tail. You usually want to process things starting at the units end, and it has a mathematical rightness (the multiplier at the nth position in the list is 10 ** n). But maybe you don't have control over your representation.

In the general case, you have a carry. If you think of your inner function as having three inputs (next digits of big number, integer to multiply by, carry) you can probably make things work.

You definitely don't want to think about functions that do something different the first time they're called! That's not a function, that's imperative programming.

Regards,

Upvotes: 3

Keith Irwin
Keith Irwin

Reputation: 5668

I would consider breaking this down differently. For instance, you could write one function which just multiplies without worrying about carrying and then a second function which handles the carrying.

As Jeffrey suggests, you could also reverse the digits, either generally, or just as needed. Although you're presumably not allowed to use the List.reverse function, you can implement that yourself in about one line of code.

Oh, and for the sake of efficiency and/or good habits, you should probably rewrite the parts which say [one value]@list to instead say (one value)::list. They'll do the same thing and the second one will be faster than the first (unless the compiler is smart enough to do this replacement for you, which it might be, in which case it will be the same speed).

Upvotes: 1

Related Questions