Hello,
Pardon if this is a repeat, I could not find a search for the forums for some reason. I’m calculating a simple recursion: 2*(t(n-1)+t(n-2)-t(n-3))+t(n-4) modulo 100_000_000. I do the calculation naively in the I do the “rem” at the end prior to saving it into an ets table which I use as a memoization table. The recursion is a monotonically increasing sequence. Issue is that when I add the “rem” operation as stated, I get a negative number. I coded it in a couple of other languages (J, Smalltalk) to see if they gave the same result but they don’t - they agree on the result and, as expected, is a positive number. Is there a limitation on the “rem” operation in Erlang that I might be missing?
Thanks!
Pete
Stackoverflow has a workaround.
And discussion about modulo of negatives: c++ - What, actually, is the modulo of a negative number? - Stack Overflow
This comes up on occasion across programming languages, and Erlang’s not unusual in differing from J and Smalltalk. Some languages (ANS Forth, Mercury) even give you both versions.
The issue is that the numbers produced by the recurrence are always positive, never negative (it comes from A181688 - OEIS if folks are curious); thus remainder with a positive modulus should not be negative.
The issue is with the memoization scheme. Using the same scheme isn’t a problem with J, or smalltalk, or Go, or Crystal; so it must be something I’m not quite understanding yet in Erlang. Apologies for the noise.
Can you post the actual runnable code?
So we can be sure that there is not some mistake in your code.
Otherwise, if really positive modulo positive gives a negative then something is not working correctly.
For the sequence in question, the rem operation will return values that are not monotonically increasing - bad assumption from my part. It does not show until n=46. Examining the memoization table shows that some values for which a(n-3) > a(n-1)+a(n-2)+a(n-4); thus the recurrence relation 2[a(n-1)+a(n-2)-a(n-3)]+a(n-4) is < 0 for these values. Replacing ‘rem’ for the function shown in the Stackoverflow link that Jrfondren sent me fixes the issue.
Thanks.
ok. got it.
The following paper may help you understand the variety of modulo implementations possible in different programming languages
https://dl.acm.org/doi/pdf/10.1145/128861.128862
(The author proposes one particular definition of the modulo operation as the most useful (and he is right). BUT the paper also explains clearly what are the possibilities, and how some languages get it wrong. Recommended reading for all programmers)
Thank you for the paper, interesting read!
What does “I checked with Smalltalk” mean?
Smalltalk has two sets of integer division and
remainder operations:
x // y flooring division
x \ y remainder from flooring division
x quo: y truncating division
x rem: y remainder from truncating division
It is a defect in the Erlang reference manual – I just checked – that it does not specify which of at least six different meanings of “integer division” is actually intended. There is a clue, in that
X rem 2 =:= 1
is only a good way to test for an integer being odd if rem is the remainder from flooring division. Except that this example, found in an otherwise great Erlang book, is NOT a good way to test for an integer being odd, because -1 is odd but (-1) rem 2 is -1.
I have used more programming languages than I can remember, and the one rule that has kept me out of trouble is
IF you are absolutely sure that x >= 0 and y > 0
THEN go ahead and use the built-in quotient and remainder
ELSE document clearly EXACTLY which quotient and remainder
you need, add a wrapper if necessary, and TEST TEST TEST.
1 Like
Meaning that I used same algorithm but with the definition of mod:
\ aNumber
^self - (self // aNumber * aNumber)