0

I have a sum series of large numbers (of the order of $10^{15}$) as Z. I need to find out the larges multiple of 1999 that is less than or equal to Z.

Formally,

$$Z = \sum_{i}^na_i$$

where $a_i >= 10^{15}$.

I need to find $Y$ such that $1999 *Y <= Z$. Also, since, Y could be very large, it is required to find $Y$ modulo 1000000007.

What I have done so far? I have taken modulus of each $a_i$ with 1000000007 and then calculated $Z$ by taking modulus after each summation with $a_i$. Then I just tried to divide $Z$ by $1999$ to obtain $Y$. But I strongly believe, dividing directly by $1999$ is not the proper way was I am diving the "modulated" value of $Z$ rather than actual $Z$.

Please suggest the proper way to find the $Y$.

Thank you.

user3243499
  • 369
  • 5
  • 16
  • I don't see anything better than doing the sum, dividing by $1999$, and finally taking the modulus. $10^{15}$ is only about $2^{50}$ so these fit into $64$ bit integers easily. The $\bmod 1000000007$ just looks to me a way to reduce the number of digits you have to type to enter the result. – Ross Millikan Nov 20 '17 at 14:48
  • n is also high, so no data type is enough to store the sum – user3243499 Nov 20 '17 at 14:52
  • It would be a good idea to indicate what your representation limits are and roughly how big $n$ is. – Eric Towers Nov 20 '17 at 15:28

2 Answers2

1

Assuming your integral type can represent $1000000007 + 1998 = 1000002005$...

Set the accumulators $R,Y$ to zero.

For each $i$ in $[1,n]$:

  • Set $r_i \leftarrow a_i \pmod{1999}$ and $q_i \leftarrow \frac{a_i - r_i}{1999}$. We are using the division algorithm: $a_i = 1999 q_i + r_i$ for $0 \leq r_i < 1999$.
  • Set $Y \leftarrow ((Y + q_i) \pmod{1000000007})$ and $R \leftarrow R + r_i$. Updates $Y$ with the new multiples of $1999$ contributed by $a_i$, reducing modulo $1000000007$, and continues accumulating remainders in $R$.
  • If $R \geq 1999$, set $Y \leftarrow ((Y+1) \pmod{1000000007})$ and $R \leftarrow R - 1999$. When the accumulated remainders are large enough to provide another multiple of $1999$, record that fact by incrementing $Y$, reducing modulo $1000000007$, and removing that copy of $1999$ from the accumulated remainders.

The final value of $Y$ is the $Y$ that you want.

The check in the third bullet can actually be performed substantially less frequently. If you try to do so, don't forget to move all the blocks of $1999$ from $R$ to $Y$and remember to do this check one last time at the end.

Eric Towers
  • 67,037
0

It sounds like you are being asked to make a simple extended precision data type. You can write $a_i=2^{32}H_i+L_i$, sum the $H_i$ and $L_i$, divide $1999$ into the sum of the $H_i$, carry the remainder over into the sum of the $L_i$, and divide $1999$ into the result, throwing away the remainder. Then take the modulo the same way, carrying from the high to the low again. If you have more problems in the series you might want to think about building in greater capability, like having more than two pieces to a number so you can represent numbers like $2^{90}$

Ross Millikan
  • 374,822