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

[Rome]

Henning Thielemann wrote:
> 
> 
> 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.
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
> 
> 

Now I've tested whether a 40k-digit multiplication is correct by using the
type Int and it is.

Another interesting thing I've discovered is:

Prelude> length [1..1000000]
1000000
Prelude> Data.List.genericLength [1..1000000]
*** Exception: stack overflow

Maybe there is something wrong with Integer ? 

-- 
View this message in context: http://www.nabble.com/Where%27s-the-problem---tf4022913.html#a11441600
Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.