The compilator stops when i try this code of fibonacci divicibility

[jhonror]

Im trying to run this code, to find the index of fibonacci divicibility, but, when the number is to long the compiler crash, i don't know what to do , but ever that I'm trying to deal whit big numbers happen the same thing.


The data input for the problem is this :

12
433156 474750 9491049193 316 274991 891051 832757 641261 441485 533035 849421 666272 782795 324942 607967 874404 882700   374884 749511 299960

Code: Pascal  [Select][+][-]

1.  
2. program jhonror;
3.  
4. Uses strutils , Math , Classes , SysUtils;
5.  
6.  
7. Type
8.  
9.   TStringDynArray = array Of AnsiString;
10.  
11.  
12. Var vec  : TStringDynArray;
13.  
14. Procedure fillArray(cnt:LongWord; lngt :LongWord);
15. Var
16. numbrs : String ;
17. Begin
18.   If lngt > 0 Then
19.     Begin
20.       ReadLn(numbrs);
21.       vec := SplitString(numbrs,' ');
22.     End
23. End;
24.  
25.  
26. procedure divfiv (numF , numA , numB, inds , cnter , lngt : int64);
27. var  numC , sum , enter  : int64;
28. begin
29.  
30. if lngt > 0  then
31.   begin
32.   sum :=  numA + numB;
33.  
34.   enter := StrtoInt64(vec[cnter]);
35.  
36.   numC := sum - ( sum div enter) * enter;
37.  
38.   if numC = 0 then
39.     begin
40.       Write( 'num F succes' , IntToStr(numF) , ' ');
41.  }
42.       divfiv (1 , 1 , 0 , inds +1 , cnter +1 , lngt -1);
43.     end
44.   else
45.     begin
46.      
47.       divfiv (numF +1, numB , numC , inds , cnter  , lngt );
48.     end;
49. end;
50. End;
51.  
52. Procedure main;
53. Var
54.   lngt : LongWord;
55. Begin
56.   ReadLn(lngt);
57.   fillArray( 1, lngt);
58.  divfiv (1 , 1, 0, 0 , 0 , lngt);  End;
59.  
60. Begin
61.   main();
62.   readln();
63. End.
64.  

[jamie]

Try to avoid recursive code, it can make your stack run dry.

[MathMan]

Hello jhonror, welcome to the forum.

When I look at your program it seems to be a (very direct) translation from a C program. As you haven't stated what exactly happens when you run the program I do have some questions

* did you really run the program that you showed? <= I am curious because I don't think that it would compile, due to the closing curly bracket in line 41
* where exctly does the program crash, and what is the exact error returned?

I will be offline for the next 2-3 days, so don't expect a fast response.

Cheers,
MathMan

[Martin_fr]

1) You have a syntax error. Line 41: }

Maybe when you copied the code?

2)
Running with "433156 474750 9491049193 316 274991 891051 832757 641261 441485 533035 849421 666272 782795 324942 607967 874404 882700   374884 749511 299960"

Your code is "recursive". That means: The procedure "divfiv" make a call to "divfiv". This is called a "nested" call.

In your program the "nested" call, makes another "nested nested" call to "divfiv". And a "nested nested nested ..... nested" call.


Every time, when "divfiv" is called, the computer must remember:
- from where it was called
- the values of all variables: numF , numA , numB, inds , cnter , lngt, numC , sum , enter
  Because when "divfix" returns, the old values will be needed again.

Example
- running "divfiv" and sum= 123
- "divfiv" is calling "nested divfiv"
   - sum:= 789
   - "nested divfiv" ends, and returns to "divfiv"
- "divfiv" expects num=123

All this needs memory. The memory used for this is called "stack" or "callstack".
The "callstack" has a fixed size (fixed maximum amount of memory).
If this "stack" memory is full, the program crashes.

On my computer, the stack memory is full after 30000 "nested" calls.

Your program wants to make more than 100000 (hundred thousand) "nested" calls.
(I could not test more than that)


You can change that.

You do

Code: Pascal  [Select][+][-]

1.    divfiv (numF +1, numB , numC , inds , cnter  , lngt );

Better do

Code: Pascal  [Select][+][-]

1. repeat
2. ...
3.   else begin
4.     numF := numF+1
5.     numA := numB;
6.     numB := numC
7.   end;
8. until numC = 0;
9.  

This is not complete.
You have to write down (see below) what your code does.
Then you can see, what you need to change.

Print out your code on paper.
On each line, write the value of the variables.
See what happens.
- compare what happens when you do "divfiv (numF +1, " and when you do "repeat"

You can use the debugger, to get the values. But write them on a paper, together with each line of code.

[Bart]

I'm just a little curious: what exactly is the program supposed to do?
It's not immediately obvious to me.

Bart

[winni]

Hi!

Mister Finbonacci and his number games ....

That is his aim:

https://math.stackexchange.com/questions/589232/fibonacci-divisibility/589247

Beside a lot of number stuff: He was the one who brought the zero to Europe.

Winni

[Bart]

So the question is wether the input number is a factor of any Fib number?
Knowing that Fib(93) = 12200160415121876738 (where Fib(0) = 0, Fib(1) = 1) and the nex one will be > High(QWord), you quite fast run out of possibilities to test, unless you have some BigInt type of library.

Bart

[winni]

Yeah -that was the advantage in the days of Fibonacci:

He was not restricted to 64 bit .
He had enough paper to write on ......

Winni

[Bart]

My own library for really big integer numbers (up to 2G digits) does calculation the same way I learned it in school with pencil and paper 

But that's getting rather off-topic.

Back to the original code: what is the meaning of all the paramters in divfiv()?

Bart

[munair]

One of the laws of recursion states that there must be a base case and that "a base case is typically a problem that is small enough to solve directly."

[Bart]

OK, AFAICS the Array holds number of which we want to know wether they are a factor of some Fibonacci number.

The routine calculates Fibonacci numbers modulo the imput number because of reasons explained in https://math.stackexchange.com/questions/589232/fibonacci-divisibility/589247.
So we are not limited to High(QWord) for the maximum value of a given Fib number we can examine.

As others have explained: do not do that recursively.

Some observations:

• numC := sum - ( sum div enter) * enter; is equal to NumC := sum mod enter;
• Use a dynamic array of some integer type, not strings. Since you need to convert to integer anyway.
• Expecting the user to input X amount of numbers without giving some feedback on the console is a bit odd...
• If the user enters more or less numbers then the value of lngt, you're in for a surprise.

Bart

[Thaddy]

https://wiki.freepascal.org/Fibonacci_number has both recursive and iterative solutions.
You can also grow the stack size of course , but I would prefer - as already mentioned -the iterative solution.

I explained handling the stacksize here: https://forum.lazarus.freepascal.org/index.php/topic,34989.msg231167.html#msg231167