Is this look-ahead adder SCOOPable?

[jjj]

Question to the SCOOP experts out there:

I have a class BIG_NUMBER implemented as an ARRAY [NATURAL_8] where each array `item' represents a "digit" in base-256.  To naively add two numbers, a and b:

loop

        sum [i] := a [i] + b [i] + carry

        if sum [i] < a [i] then      -- NATURAL wraps around past zero if too big

            carry := 1

        else

            carry := 0

        end

        i := i + 1

end

The above algorithm is O(n), because the value of a particular digit must know the carry-in from the previous calculation, requiring the carry calculation to propagate from low-order to high-order digit.  But, can we add all the digits concurrently, similarly to a carry look-ahead adder, in O(1) time?

We know, without looking at the whole number, that the addition of two digits at a particular place in the numbers will "generate" a carry to the next place if that sum is greater than the base.  Using NATURAL_8 the sum of two digits wraps around past zero if the sum is greater than 255 so that the sum is less than both [or either] of the digits.  We also can determine from the two digits if that sum could "propagate" a carry (i.e. there will be a carry-out if there was a carry-in).   For NATURAL_8 that happens if the sum of the digits is equal to 255, because adding one from a carry-in makes the sum zero with a carry-out of one.  So:

sum [i] := a[i] + b[i] + carry (a, b, i - 1)

where feature `carry' is something like:

    carry (a_num, a_other: BIG_NUMBER; index: INTEGER): NATURAL_8

            -- The carry-out generated at the `index'th digits of the two numbers

        local

            s: NATURAL_8 

        do

            s := a_num [i] + a_other [i]

            if s < a_num [i] or else

                s = 255 and then carry (a_num, a_other, index - 1) = 1 then  

                    Result := 1

            end

        end

            

So, my question.  Is there a way to parallel this computation with SCOOP?  What objects are separate, one or both BIG_NUMBERs?  the Result of the computation?  the indexes?  What is signature of the separate calls and declarations? 

Thanks for reading this far,

jjj

[Alexander Kogtenkov]

Unless the numbers have thousands/millions of digits making the addition using SCOOP would not make the program faster. It would be much more efficient to use NATURAL_64 instead of NATURAL_8 instead. Also, an optimized implementation for a specific number length could make the difference, e.g. if there is BIG_NUMBER_256, implemented with 4 NATURAL_64, it would work better than the general implementation. Creating a separate region for a digit is too costly.

 

Alexander Kogtenkov

 

 

jjj <jjj...@uky.edu>:
 

--
You received this message because you are subscribed to the Google Groups "Eiffel Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to eiffel-users...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/eiffel-users/80016e79-c9de-4cc0-81d5-9b91f8f803a7n%40googlegroups.com.

 

[Finnian Reilly]

I have a class BIG_NUMBER implemented as an ARRAY [NATURAL_8] where each array `item' represents a "digit" in base-256.  To naively add two numbers, a and b:

Maybe class INTEGER_X found in "$ISE_EIFFEL/contrib/library/math/eapml/eapml.ecf" already has what you need?

[jjj]

Yes, NATURAL_8 was for illustration only.

"a separate region for each digit is too costly."  Sure, but I just wanted to know if it were possible and how to do it, so I could better understand SCOOP.

I thought perhaps a look-ahead for a segment of digits, where a normal add within the segment.
jjj

[jjj]

Hey, thanks.  Will look at that.  But I'm still curious if about SCOOP

jjj

[Ulrich Windl]

>>> jjj <jjj...@uky.edu> schrieb am 20.02.2021 um 03:48 in Nachricht
<80016e79-c9de-4cc0...@googlegroups.com>:

> Question to the SCOOP experts out there:
>
> I have a class BIG_NUMBER implemented as an ARRAY [NATURAL_8] where each
> array `item' represents a "digit" in base-256. To naively add two numbers,
> a and b:
>
> loop
> sum [i] := a [i] + b [i] + carry
> if sum [i] < a [i] then -- NATURAL wraps around past zero if
> too big
> carry := 1
> else
> carry := 0
> end
> i := i + 1
> end
>
> The above algorithm is O(n), because the value of a particular digit must
> know the carry-in from the previous calculation, requiring the carry
> calculation to propagate from low-order to high-order digit. But, can we
> add all the digits concurrently, similarly to a carry look-ahead adder, in
> O(1) time?

I think if you can add arbitrary large numbers in O(1) you'd be the crypto champ ;-)