On Wed, 4 Jul 2007, Rome wrote:
I write a program for fast online multiplication, this means, leading digits are computed first, so this program is able to handle real numbers.
My program and Source-Code is available under http://www.romeinf04.de http://www.romeinf04.de
but only with german comments, because this is my master thesis.
Now the problem: My program computes using the schoenhage-strassen multiply-subroutine the output everytime only until the 32777th Digit, but then it holds without an error message. Windows Task manager tells me CPU Usage 100% and Memory Allocation is increasing.
This sounds like an unresolvable data dependency. E.g. a digit depends via some other variables on its own value or it depends on an infinite number of other digits.
Profiling told me, the function Algorithm.resultOfMult is using this memory. To compute the 32777th digit, my program needs several digits of the input-numbers including the 32800th. I'm using GHC 6.6.1 with option -O2 to compile.
Output is row-wise by an IO-function, calling itself recursively with updated parameters, hte output looks like:
dig11 dig21 --> res1 dig12 dig22 --> res2 dig12 dig23 --> res3 . . . and so on
If I use the Naive-Multiply-Subroutine, the problem occurs at the 16392th digit.
A friend of mine compiled it under Linux and got: . . . 32779 : 1 1 ---32776--> 0 32780 : 1 0 ---32777--> -1 Main: Ix{Integer}.index: Index (32766) out of range ((0,32765))
If I convert every Integer into Int and use instead of the generic list functions the prelude-list functions, it works.
... and the result is right?
I don't have any idea, where the problem might be...
Stupid question: Did you pay enough attentation to carries? There might be an unresolvable dependency if you request a digit which depends on infinitely many carries from following digits. If you like to compare with other implementations of real numbers, see: http://www.haskell.org/haskellwiki/Applications_and_libraries/Mathematics#Re...