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

Henning Thielemann lemming at henning-thielemann.de
Wed Jul 4 15:09:41 EDT 2007

```On Wed, 4 Jul 2007, Rome wrote:

> > 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.
>

You are probably aware of the common problems related to computation with
real numbers, thus my replies below might not be of much help. I assume
that your problem is specific to your code and the solution requires
time in either of these, so far.

> The next output-digit depends on several digits of the input, which are
> determined by the rectangles defined in module /Schedule/. Every coordinate
> of a single rectangle is unique by definition.
> Because I use Signed-Digit-Representation, carries are only local in a
> single call of the multiplication -subroutine.

If you add at least 100 numbers in base 10 computation, then two carry
steps become necessary, both with signed and unsigned digits.

> Further my program is the implementation of an online-algorithm, leading
> digits are computed first, so an infinte number of carries shouldn't be
> the reason, I think.

At some time, you have to apply carries, otherwise digits will get out of
range. You might want to make perfect carries by processing the digit
stream from the right to left - which is obviously impossible and you have