Talk:Subtract with carry

I was looking at the ranlux random number generator. However, looking only briefly, I saw it is implemented with a subtract-with-carry-engine. However, I've also heard about luxury levels. I don't see how luxury levels fit into the subtract with carry. Couple someone with more knowledge please either create a wiki page for the ranlux random number generator or point out how luxury levels fit into the subtract with carry generators?

Less Technical Explanation

In response to the flag: "This article may be too technical for most readers to understand", I have written an easier explanation, as follows:

The algorithm generates a series of numbers x(1), x(2), x(3), ... x(i-1), x(i), ...

where x(1) is the first value issued; x(2) is the second, and so on; x(i) is the newest value issued; x(i-1) is the one just previous.

The sequence may be described by a recurrence relation:

y(i) = x(i−S) − x(i−R) − cy(i−1)
cy(i) = 1 if y(i) < 0; otherwise cy(i) = 0
x(i) = y(i) mod M

where x(i-S) is a previous value, S iterations back; x(i-R) is a previous value, R iterations back; (R is father back than S), and y(i) is an intermediate result gotten by subtracting x(i-R) from x(i-S), figuring in the carry cy(i-1) (actually the borrow) from the previous iteration.

cy(i) is the newest carry out. It is saved for the next iteration.

mod M means that if the subtraction result is a number too large, it is trimmed. For instance, if we are doing these computations with 8-bit registers holding 2's complement numbers, the allowed values would be -128 (1000 0000 in binary) to +127 (0111 1111). If we subract say 100 (0110 0100) from -120 (1000 1000), the result would be -220 (1 0010 0100), which would not fit in the register. It would get trimmed to the rightmost 8 bits 0010 0100 (36 decimal) and the leftmost "1" bit would be the carry out.

M in this case would be 2^8 = 256. 8 is the size of the registers in bits. M is chosen thus to be very convenient since the registers in computers are 8, 16, 32, or 64 bits wide and the mod operation is automatic. If M were some number like 119 the algorithm would require actual division and would take more time.

I hesitate to install this and I don't know how to remove the flag and I don't have time to learn how, so I leave it to someone else. Also now that I read it over it might actually be more dizzying than what's already there... Friendly Person (talk) 16:44, 1 December 2019 (UTC)