I am implementing a recursive program to calculate the certain values in the Schroder sequence, and I'm having two problems:

1. I need to calculate the number of calls in the program;
2. Past a certain number, the program will generate incorrect values (I think it's because the number is too big);

Here is the code:

let rec schroder n = 
  if n <= 0 then 1
  else if n = 1 then 2
  else 3 * schroder (n-1)   sum n 1 
and sum n k = 
  if (k > n-2) then 0 
  else schroder k * schroder (n-k-1)   sum n (k 1)

When I try to return tuples (1.), the function sum stops working because it's trying to return int when it has type int * int; Regarding 2., when I do schroder 15 it returns: -357364258 when it should be returning 3937603038.

CodePudding user response：

I need to calculate the number of calls in the program; ... the function 'sum' stops working because it's trying to return 'int' when it has type 'int * int'

Make sure that you have updated all the recursive calls to shroder. Remember it is now returning a pair not a number, so you can't, for example, just to add it and you need to unpack the pair first. E.g.,

...
else 
  let r,i = schroder (n-1) (i 1) in
  3 * r   sum n 1 and ...

and so on.

Past a certain number, the program will generate incorrect values (I think it's because the number is too big);

You need to use an arbitrary-precision numbers, e.g., zarith

CodePudding user response：

This is the third time I've seen this problem here on StackOverflow, so I assume it's some kind of school assignment. As such, I'm just going to make some comments.

1. OCaml doesn't have a function named sum built in. If it's a function you've written yourself, the obvious suggestion would be to rewrite it so that it knows how to add up the tuples that you want to return. That would be one approach, at any rate.

2. It's true, ints in OCaml are subject to overflow. If you want to calculate larger values you need to use a "big number" package. The one to use with a modern OCaml is Zarith (I have linked to the description on ocaml.org).

However, none of the other people solving this assignment have mentioned overflow as a problem. It could be that you're OK if you just solve for representable OCaml int values.

CodePudding user response：

3937603038 is larger than what a 32-bit int can hold, and will therefore overflow. You can fix this by using int64 instead (until you overflow that too). You'll have to use int64 literals, using the L suffix, and operations from the Int64 module. Here's your code converted to compute the value as an int64:

let rec schroder n = 
  if n <= 0 then 1L
  else if n = 1 then 2L
  else Int64.add (Int64.mul 3L (schroder (n-1))) (sum n 1)

and sum n k =
  if (k > n-2) then 0L
  else Int64.add (Int64.mul (schroder k) (schroder (n-k-1))) (sum n (k 1))