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

[Henning Thielemann]

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.
>
> Thx for your reply.

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
understanding your algorithm and your implementation, I didn't invested
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
to follow a different strategy.

> In my opinion there is something wrong with the use of Integer because of
> the Linux-error message.
> I can only verify the correctness of the result of the first 30
> output-digits, and these are okay in both cases: Int and Integer.

You can verify correctness for any multiplication by multiplying huge
Integers.