CODEWITHSUNDEEP
recursionmathocamllargenumber
just likethis
just likethis

Reputation: 1

Schroders Big number sequence

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.

EDIT:

firstly thanks for the tips, secondly after some hours of deep struggle, i manage to create the function, now my problem is that i'm struggling to install zarith. I think I got it installed, but ..

  1. in terminal when i do ocamlc -I +zarith test.ml i get an error saying Required module 'Z' is unavailable.

  2. in utop after doing #load "zarith.cma";; and #install_printer Z.pp_print;; i can compile, run the function and it works. However i'm trying to implement a Scanf.scanf so that i can print different values of the sequence. With this being said whenever i try to run the scanf, i dont get a chance to write any number as i get a message saying that '\\n' is not a decimal digit.

With this being said i will most probably also have problems with printing the value, because i dont think that i'm going to be able to print such a big number with a %d. The let r1,c1 = in the following code, is a example of what i'm talking about.

Here's what i'm using :

(function)
..
let v1, v2 = Scanf.scanf "%d %d" (fun v1 v2-> v1,v2);;

let r1,c1 = schroder_a (Big_int_Z.of_int v1) in
Printf.printf "%d %d\n" (Big_int_Z.int_of_big_int r1) (Big_int_Z.int_of_big_int c1);

let r2,c2 = schroder_a v2 in
Printf.printf "%d %d\n" r2 c2;

P.S. 'r1' & 'r2' stands for result, and 'c1' and 'c2' stands for the number of calls of schroder's recursive function.

P.S.S. the prints are written differently because i was just testing, but i cant even pass through the scanf so..

Upvotes: 0

Views: 199

Answers (3)

glennsl
glennsl

Reputation: 29126

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))

Upvotes: 2

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66823

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.

Upvotes: 2

ivg
ivg

Reputation: 35270

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

Upvotes: 1

Related Questions