CODEWITHSUNDEEP
javamethodsadditionmodulo
ilja
ilja

Reputation: 79

The method add mod 2^512

It's add modulo 2^512. Could you explain me why we doing here >>8 and then &oxFF? I know i'm bad in math.

int AddModulo512(int []a, int []b)
{
    int i = 0, t = 0;
    int [] result = new int [a.length];
    for(i = 63; i >= 0; i--)
    {
        t = (a[i]) + (int) (b[i]) + (t >> 8);
        result[i] = (t & 0xFF);    //?
    }
    return result;
}

Upvotes: 3

Views: 342

Answers (5)

Brian Truong
Brian Truong

Reputation: 1

I think your question misses a very important part, the data format, i.e. how data are stored in a[] and b[]. To solve this question, I make some assumptions:

  • Since it's modulo arithmetic, a, b <= 2^512. Thus, a and b have 512 bits.
  • Since a and b have 64 elements, only 8 right-most bits of each elements are used. In other words, a[i], b[i] <= 256.

Then, what remains is very straightforward. Just consider each a[i] and b[i] as a digit (each digit is 8-bit) in a base 2^512 addition and then perform addition by adding digit-by-digit from right-to-left.

t is the carry variable which stores the value (with carry) of the addition at the last digit. t>>8 throws a way the right-most 8 bits that has been used for the last addition which is used as carry for the current addition. (t & 0xFF) gets the right-most 8 bits of t which is used for the current digit.

Since it's modulo addition, the final carry is thrown away.

Upvotes: 0

rgettman
rgettman

Reputation: 178263

It looks like you have 64 ints in each array, but your math is modulo 2^512. 512 divided by 64 is 8, so you are only using the least significant 8 bits in each int.

Here, t is used to store an intermediate result that may be more than 8 bits long.

In the first loop, t is 0, so it doesn't figure in the addition in the first statement. There's nothing to carry yet. But the addition may result in a value that needs more than 8 bits to store. So, the second line masks out the least significant 8 bits to store in the current result array. The result is left intact to the next loop.

What does the previous value of t do in the next iteration? It functions as a carry in the addition. Bit-shifting it to the right 8 positions makes any bits beyond 8 in the previous loop's result into a carry into the current position.

Example, with just 2-element arrays, to illustrate the carrying:

[1, 255] + [1, 255]

First loop:

t = 255 + 255 + (0) = 510;     // 1 11111110
result[i] = 510 & 0xFF = 254;  //   11111110

The & 0xFF here takes only the least significant 8 bits. In the analogy with normal math, 9 + 9 = 18, but in an addition problem with many digits, we say "8 carry the 1". The bitmask here performs the same function as extracting the "8" out of 18.

Second loop:

// 1 11111110 >> 8 yields 0 00000001
t = 1 + 1 + (510 >> 8) = 1 + 1 + 1 = 3; // The 1 from above is carried here.
result[i] = 3 & 0xFF = 3;

The >> 8 extracts the possible carry amount. In the analogy with normal math, 9 + 9 = 18, but in an addition problem with many digits, we say "8 carry the 1". The bit shift here performs the same function as extracting the "1" out of 18.

The result is [3, 254].

Notice how any carry leftover from the last iteration (i == 0) is ignored. This implements the modulo 2^512. Any carryover from the last iteration represents 2^512 and is ignored.

Upvotes: 3

Rand
Rand

Reputation: 321

The mathematical effect of a bitwise shift right (>>) on an integer is to divide by two (truncating any remainder). By shifting right 8 times, you divide by 2^8, or 256.

The bitwise & with 0xFF means that the result will be limited to the first byte, or a range of 0-255.

Not sure why it references modulo 512 when it actually divides by 256.

Upvotes: 3

Captain Man
Captain Man

Reputation: 7695

Upvotes: 2

Chris Stillwell
Chris Stillwell

Reputation: 10547

>> is a bitwise shift.

The signed left shift operator "<<" shifts a bit pattern to the left, and the signed right shift operator ">>" shifts a bit pattern to the right. The bit pattern is given by the left-hand operand, and the number of positions to shift by the right-hand operand. The unsigned right shift operator ">>>" shifts a zero into the leftmost position, while the leftmost position after ">>" depends on sign extension.

& is a bitwise and

The bitwise & operator performs a bitwise AND operation.

https://docs.oracle.com/javase/tutorial/java/nutsandbolts/op3.html

http://www.tutorialspoint.com/java/java_bitwise_operators_examples.htm

Upvotes: 2

Related Questions