「テンプレート:Modint」の版間の差分
細 (1版) |
(相違点なし)
|
2015年3月14日 (土) 12:15時点における最新版
This template gives a version of the modulo operator. It gives the remainder of division after truncating both operands to an integer. Unlike parser function mod it gives non-negative values only.
The template was created because that parser function used to be unreliable when the second parameter was 2^31-1 or more. For this template, if the 2nd parameter is greater than ca. 2^63-2000, the sum of the parameters should not exceed 2^63-1.
Special care is taken for the case that the dividend is very close to the maximum, because the quotient of integers is, if not an integer, rounded to a float; if the rounding is upward, then multiplying by the divisor could give a result above the maximum, in which case this multiplication would not be exact. To avoid that, in Template:Modint/1 the numerator of the quotient is reduced by 2000, higher than the possible rounding error in rounding to the float in this case. This makes the value of the result of that template on average 2000 higher, and possibly more than the divisor, but in the second stage of the computation, by Template:Modint, this does not cause any complication.[1]
- Usage:
- {{modint|dividend|divisor}}
Examples
{{modint|40|10}}→ 0{{modint|-40|10}}→ 0{{modint|40|-10}}→ 0{{modint|-40|-10}}→ 0{{modint|123|10}}→ 3{{modint|-123|10}}→ 7{{modint|123|-10}}→ 3{{modint|-123|-10}}→ 7{{modint|123|(2^32-1)}}→ 123; compare:{{#expr:123mod(2^32-1)}}→ 123 (wrong)
{{modint|1567856476567843242|1e18}}→ 567856476567843328 (input rounded to float, output as type integer){{modint|2^63-1024|1e18}}→ 223372036854774784 (input is representable as float, therefore exact result){{modint|2^62|100}}→ 4{{modint|123|trunc(2^63-1024)+trunc1023}}→ 0{{modint|trunc(2^63-1024)+trunc1023|1e18}}→ 223372036854775807
{{modint|trunc(1e18/7)|1e17}}→ 42857142857142864; the inaccuracy is not in modint, but in the division:{{numf|1e18/7}}→ 142,857,142,857,142,860
{{#expr:trunc(2^63-2^10)+trunc1023}}→ 9223372036854775807{{numf|trunc(2^63-2^10)+trunc1023}}→ 9,223,372,036,854,776,000
{{numf|trunc(2^63-1024)+trunc1023}}→ 9,223,372,036,854,776,000
{{modint|trunc(2^63-1024)+trunc1023|1}}→ 0{{modint|trunc(2^63-1024)+trunc1023|10}}→ 7{{modint|trunc(2^63-1024)+trunc1023|100}}→ 7{{modint|trunc(2^63-1024)+trunc1023|1e3}}→ 807{{modint|trunc(2^63-1024)+trunc1023|1e4}}→ 5807{{modint|trunc(2^63-1024)+trunc1023|1e5}}→ 75807{{modint|trunc(2^63-1024)+trunc1023|1e6}}→ 775807{{modint|trunc(2^63-1024)+trunc1023|1e7}}→ 4775807{{modint|trunc(2^63-1024)+trunc1023|1e8}}→ 54775807{{modint|trunc(2^63-1024)+trunc1023|1e9}}→ 854775807{{modint|trunc(2^63-1024)+trunc1023|1e10}}→ 6854775807{{modint|trunc(2^63-1024)+trunc1023|1e11}}→ 36854775807{{modint|trunc(2^63-1024)+trunc1023|1e12}}→ 36854775807{{modint|trunc(2^63-1024)+trunc1023|1e13}}→ 2036854775807{{modint|trunc(2^63-1024)+trunc1023|1e14}}→ 72036854775807{{modint|trunc(2^63-1024)+trunc1023|1e15}}→ 372036854775807{{modint|trunc(2^63-1024)+trunc1023|1e16}}→ 3372036854775807{{modint|trunc(2^63-1024)+trunc1023|1e17}}→ 23372036854775807{{modint|trunc(2^63-1024)+trunc1023|1e18}}→ 223372036854775807
Third digit from the right:
{{numf|floor({{modint|trunc(2^63-1024)+trunc1023|1e3}}/1e2)}}→ 8
Numbers greater than 2^63-1
The template is based on exact integer-type multiplication of two integers with a product near the first parameter. However, if the first parameter is greater than 2^63-1, the product is above that maximum, and rounded to float.
{{modint|1e23|1}}→ 0{{modint|1e23|10}}→ 0{{modint|1e23|100}}→ 0{{modint|1e23|1e3}}→ 0{{modint|1e23|1e4}}→ 0{{modint|1e23|1e5}}→ 0{{modint|1e23|1e6}}→ 0{{modint|1e23|1e7}}→ 0{{modint|1e23|1e8}}→ 83886080{{modint|1e23|1e9}}→ 989855744{{modint|1e23|1e10}}→ 0{{modint|1e23|1e11}}→ 99992207360{{modint|1e23|1e12}}→ 999989182464{{modint|1e23|1e13}}→ 0{{modint|1e23|1e14}}→ 99999991988224{{modint|1e23|1e15}}→ 999999986991104{{modint|1e23|1e16}}→ 0{{modint|1e23|1e17}}→ 99999999990956032{{modint|1e23|1e18}}→ 999999999993446400
{{modint|999999999993446400|2^24}}→ 0{{numf|999999999993446400/2^24}}→ 59,604,644,775
The spacing of floats in the range 1e23 is:
{{numf|2^24}}→ 16,777,216
so we can expect an error up to 8e6. The answer is the float value to which 1e23 is rounded (99,999,999,999,999,991,611,392), minus the float value to which 99999e18 is rounded:
{{numf|1e23}}→ 100,000,000,000,000,000,000,000
{{numf|99999e18}}→ 99,999,000,000,000,000,000,000{{numf|1e23-99999e18}}→ 999,999,999,993,446,400{{hex|1e23}}→1.52d02c7e14af6hex*2^76{{hex|99999e18}}→1.52cf4e72a974fhex*2^76{{hex|1e23-99999e18}}→1.bc16d674e0000hex*2^59
See also
- ↑ Former demo: Template:Modint/demo.