# Modulo and division on representation: amount * limit + offset.

• May 19th 2013, 12:58 PM
indieExe
Modulo and division on representation: amount * limit + offset.
Representation: amount * limit + offset, where the result of amount * limit + offset cannot be directly accessed.

Code:

`(((amount * (limit % radix)) % radix) + (offset % radix)) % radix`
is how to do modulo on representation amount * limit + offset without directly accessing amount * limit + offset.

amount is the amount of limit you have, offset is a number >= 0 and <= limit. Offset, amount and limit are whole numbers.

Division i cannot figure out, please help me(not to just dump everything on you, but i am unable to figure it out).
• May 19th 2013, 10:54 PM
chiro
Re: Modulo and division on representation: amount * limit + offset.
Hey indieExe.

Can you explain in plain word what you want to find (like an equation), what you are given (and the format its in) and what you can use (and the format its in)?
• May 20th 2013, 06:13 AM
indieExe
Re: Modulo and division on representation: amount * limit + offset.
The division needs to be done in two separate parts.

1. Calculate new offset.
2. Calculate new amount.
(The order doesn't really matter, i think).

(considering these are all positive real numbers)
new_amount = ((n/limit) * amount) + ((offset/n)/limit). This would give the amount n would repeat in limit * amount + offset.

new_offset = (float new_amount - int new_amount) * ???

new_amount = int new_amount.

I think this would be correct. Now the remnants of new_amount is the new_offset.
But how do i retrieve the new_offset?

(I don't really know what you mean by format, and does plain word mean in this context?)
• May 20th 2013, 02:00 PM
indieExe
Re: Modulo and division on representation: amount * limit + offset.
Plain word:
How do one calculate the division: (limit * amount + offset) / n, when amount is the amount of limit one currently have, offset is a number >= 0 and <= limit,
and when one cannot obtain the result of (limit * amount + offset) / n directly because one can only operate on a number <= limit.

The result of the division should be put into in the format: new_amount * limit + new_offset.
• May 23rd 2013, 06:34 PM
indieExe
Re: Modulo and division on representation: amount * limit + offset.
Did you want to help me or not?
• May 23rd 2013, 07:11 PM
chiro
Re: Modulo and division on representation: amount * limit + offset.
So if you have a number N and want to get it in form (limit,amount,offset) then calculate

integer(N/limit) for amount. Take this value and calculate
N - amount*limit for offset.

In C++ this is basically offset = N%limit and amount = (N - offset)/limit.
• May 23rd 2013, 08:51 PM
johng
Re: Modulo and division on representation: amount * limit + offset.
Hi,
Let me see if I understand your question. You want to do integer arithmetic and for ints limit, amount and n you want to compute (amount*limit)/n and (amount*limit)%n even when the product amount*limit results in overflow. That is, if max is the largest possible int (in C INT_MAX or Java Integer.MAX_INT) and amount*limit exceeds max, you still want the correct int values.

In a high level language, at least the ones that I know, there is no indication of overflow. So the only solution is to do multi-precision arithmetic. I've kind of lost track of the standard C++ library, but I know in Java the class BigInteger will do the desired arithmetic. You just have to switch from ints to BigInteger instances. Alternatively, you can write your own multi-precision routines specifically to handle the problem as I understand it. I've written my own big integers in both C++ and Java. It turns out that the hardest thing to do is division and remaindering for big integers. So, my advice is to use some "canned" multi-precision routines if you can.