Lazarus

Free Pascal => General => Topic started by: jhonror on December 29, 2021, 07:44:43 pm

Title: The compilator stops when i try this code of fibonacci divicibility
Post by: jhonror on December 29, 2021, 07:44:43 pm
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.  


Title: Re: The compilator stops when i try this code of fibonacci divicibility
Post by: jamie on December 29, 2021, 11:24:28 pm
Try to avoid recursive code, it can make your stack run dry.
Title: Re: The compilator stops when i try this code of fibonacci divicibility
Post by: MathMan on December 30, 2021, 12:13:42 pm
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
Title: Re: The compilator stops when i try this code of fibonacci divicibility
Post by: Martin_fr on December 30, 2021, 01:16:28 pm
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.
Title: Re: The compilator stops when i try this code of fibonacci divicibility
Post by: Bart on December 30, 2021, 05:40:29 pm
I'm just a little curious: what exactly is the program supposed to do?
It's not immediately obvious to me.

Bart
Title: Re: The compilator stops when i try this code of fibonacci divicibility
Post by: winni on December 30, 2021, 05:53:47 pm
Hi!

Mister Finbonacci and his number games ....

That is his aim:

https://math.stackexchange.com/questions/589232/fibonacci-divisibility/589247 (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
Title: Re: The compilator stops when i try this code of fibonacci divicibility
Post by: Bart on December 30, 2021, 06:20:18 pm
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
Title: Re: The compilator stops when i try this code of fibonacci divicibility
Post by: winni on December 30, 2021, 06:31:18 pm
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
Title: Re: The compilator stops when i try this code of fibonacci divicibility
Post by: Bart on December 30, 2021, 06:51:16 pm
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  O:-)

But that's getting rather off-topic.

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

Bart
Title: Re: The compilator stops when i try this code of fibonacci divicibility
Post by: munair on December 30, 2021, 06:53:15 pm
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."
Title: Re: The compilator stops when i try this code of fibonacci divicibility
Post by: Bart on December 30, 2021, 07:35:08 pm
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 (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:

Bart
Title: Re: The compilator stops when i try this code of fibonacci divicibility
Post by: Thaddy on January 09, 2022, 07:35:41 am
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
TinyPortal © 2005-2018