[Haskell-cafe] Re: Deadlock in real number multiplication (Was: Where's the problem ?)

[Henning Thielemann]

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#Real_and_rational_numbers