ProcedureReturn with Double only in 8 levels?

[FihmpenRouk]

Hi!

I have found a curios problem with Procedures.

When using Longs i can recurs a number of levels, but with Doubles it stops at 8 calls. I can't figure out why. Anyone, else who can?

code with Long:

Code: Select all

Define.l

Procedure.l fac_rec(n)
	Debug n
  If n > 1
    ProcedureReturn n * fac_rec(n - 1)
  EndIf
  ProcedureReturn 1 
EndProcedure

MessageRequester("faculty with true recursion",Str(fac_rec(12)))

Debug will show a countdown to 1 and the program will return with the correct result 479001600.

same code with Double:

Code: Select all

Define.d

Procedure.d fac_rec(n)
	Debug n
  If n > 1
    ProcedureReturn n * fac_rec(n - 1)
  EndIf
  ProcedureReturn 1 
EndProcedure

MessageRequester("faculty with true recursion",Str(fac_rec(12)))

Debug will show a countdown to 5, then -1#IND and return the result -9223372036854775808.
#IND I suppose is Indefinite, but I suspect it's the ProcedureReturn from the called Procedure that returns it.

Or have I managed to do something that shouldn't be possible? It works a while but suddenly breaks down - after exactly 8 levels. Change the value to 32 and it will count down to 25 and so on.

Well, here is some code that makes it work suddenly:

Code: Select all

Define.d

Procedure.d fac_rec(n)
	Debug n
  If n > 1
  	result = fac_rec(n - 1)
    ProcedureReturn n * result
  EndIf
  ProcedureReturn 1 
EndProcedure

MessageRequester("faculty with true recursion",Str(fac_rec(12)))

And, woola, it works. But why? I only put the result in a variable before returning it.

If this has been handled before somewhere, I'm very sorry, but i have been searching and didn't find anything like this.

[Kaeru Gaman]

the problem with directly using ProcedureReturn was reported before.
I don't know what exactly causes it, and how it could be repaired...
but I want to believe there is a reason why Fred did not fix it yet.
interesting you found it happens after 8 levels.
I don't think the stack is full after 8 Procs with such few local variables, so it must be something else.

for now, better use a Dummy to put the result in first and only return the Dummy.
I would even drag the last mult out:

Code: Select all

     result = n * fac_rec(n - 1)
    ProcedureReturn result

[srod]

The problem (not really a bug) is that the fpu only has a stack of 8 registers and these are being used to hold the individual return values from the recursive calls to your function. After 8 such calls you run out of registers.

Your last code circumvents this problem by moving the return value into a local variable immediately after calling the function again (thus freeing the top most fpu register because it is placing the value on the normal stack - in the 'result' variable) whilst your previous snippet does not and instead holds it upon the fpu register stack.

The only real way Purebasic could fix this would be by not leaving floating point function returns in the fpu ST0 register etc. but this would slow things down for certain routines.

[Kaeru Gaman]

thanks!

whoo now I know why...

[FihmpenRouk]

@srod: Thanks for that explanation! That clears it up.

Lucky, I didn't report it as a bug then. But I actually thought there *could* be some other unknown factor behind it.

Very nice!

[Trond]

Actually it's a bug, because PB treats the fpu registers as volatile in expressions, but non-volatile in calls. (I.e. expecting the called function to save them, but not actually saving them in the called function.) This isn't really correct, as they have to be either volatile everywhere (stdcall) or non-volatile everywhere.

[charvista]

Interesting. So this is probably a "Stack Overflow"....
I understand that Fred might have his reasons for keeping high speed by not fixing this (yet), but when a "Stack Overflow" occurs, it should be "repaired" internally, even at the cost of speed, because it is still better to get correct values at a lower speed rather than high speed with incorrect values.
Or then, the PureBasic's compiler should consider as illegal to perform calculations at the ProcedureReturn level to guarantee correct values. This is the safest, I think.

[Trond]

Or then, the PureBasic's compiler should consider as illegal to perform calculations at the ProcedureReturn level to guarantee correct values. This is the safest, I think.

It's only a problem when doing floating point calculation and using procedure calls in the expression.

[blueznl]

Weeeeelllllll..... to me this is a bug, frankly. It's a limitation which, frankly, isn't that logical... (From a logic perspective, I understand why it happened, but why should integers be treated differently from floats?)

I'd like to suggest to either properly document it , make floats behave like ints (ie. no limits) or give a compiler 'optimisation' option, allowing to toggle this behaviour.

My 2 cents...

[FihmpenRouk]

I follow what you are writing here and my few cents to the matter is:
What was the original thoughts behind this? It seems to me that doubles are handled like this because of a deliberate plan ...
... but, perhaps that the compiler should show at least a warning? If there were a warning, nobody could think of it as a bug anymore.

Even if it's not a bug, it's a pretty mean feature if you're not aware of it. I could imagine what would happen in a big complex program. A small nightmare to put it mildly.

[Trond]

I follow what you are writing here and my few cents to the matter is:
What was the original thoughts behind this? It seems to me that doubles are handled like this because of a deliberate plan ...

No, it's almost surely because its quite hard to fix it without a performance hit. You see, that requires re-ordering the expression so that the n comes after the recursive call. In some cases you'll always get a performance hit.

It's definetely a bug, because this was discussed before: http://www.purebasic.fr/english/viewtop ... =recursion

[FihmpenRouk]

@Trond: A-ha. Weird, I didn't find your post before. Must assign me a crash course in search management.

[Trond]

@Trond: A-ha. Weird, I didn't find your post before. Must assign me a crash course in search management.

It's for floats so you probably didn't find it when you searched for double. I just found it because I remember posting it.