+/EE360P

distributed systems

git clone https://git.julia.blue/+/EE360P

vijaygarg1init07ca65d

master
2.8 KiB112 linesraw
1/**
2 * Licensed to the Apache Software Foundation (ASF) under one
3 * or more contributor license agreements.  See the NOTICE file
4 * distributed with this work for additional information
5 * regarding copyright ownership.  The ASF licenses this file
6 * to you under the Apache License, Version 2.0 (the
7 * "License"); you may not use this file except in compliance
8 * with the License.  You may obtain a copy of the License at
9 *
10 *     http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
17 */
18package org.apache.hadoop.examples.pi.math;
19
20/** Modular arithmetics */
21public class Modular {
22  static final long MAX_SQRT_LONG = (long)Math.sqrt(Long.MAX_VALUE);
23
24  /** Compute 2^e mod n */
25  public static long mod(long e, long n) {
26    final int HALF = (63 - Long.numberOfLeadingZeros(n)) >> 1;
27    final int FULL = HALF << 1;
28    final long ONES = (1 << HALF) - 1; 
29
30    long r = 2;
31    for (long mask = Long.highestOneBit(e) >> 1; mask > 0; mask >>= 1) {
32      if (r <= MAX_SQRT_LONG) {
33        r *= r;
34        if (r >= n) r %= n;
35      } else {
36        // r^2 will overflow
37        final long high = r >>> HALF;
38        final long low  = r &= ONES;
39        
40        r *= r;
41        if (r >= n) r %= n;
42
43        if (high != 0) {
44          long s = high * high;
45          if (s >= n) s %= n;
46          for(int i = 0; i < FULL; i++)
47            if ((s <<= 1) >= n) s -= n;
48          
49          if (low == 0)
50            r = s;
51          else {
52            long t = high * low;
53            if (t >= n) t %= n;
54            for(int i = -1; i < HALF; i++)
55              if ((t <<= 1) >= n) t -= n;
56            
57            r += s;
58            if (r >= n) r -= n;
59            r += t;
60            if (r >= n) r -= n;
61          }
62        }
63      }
64
65      if ((e & mask) != 0) {
66        r <<= 1;
67        if (r >= n) r -= n;
68      }
69    }
70    return r;
71  }
72
73  /** Given x in [0,1) and a in (-1,1),
74   * return (x, a) mod 1.0. 
75   */
76  public static double addMod(double x, final double a) {
77    x += a;
78    return x >= 1? x - 1: x < 0? x + 1: x;
79  }
80
81  /** Given 0 &lt; x &lt; y,
82   * return x^(-1) mod y.
83   */
84  public static long modInverse(final long x, final long y) {
85    if (x == 1) return 1;
86
87    long a = 1;
88    long b = 0;
89    long c = x;
90
91    long u = 0;
92    long v = 1;
93    long w = y;
94    
95    for(;;) {
96      {
97        final long q = w/c;
98        w -= q*c;
99        u -= q*a;
100        if (w == 1) return u > 0? u: u + y;
101        v -= q*b;
102      }
103      {
104        final long q = c/w;
105        c -= q*w;
106        a -= q*u;
107        if (c == 1) return a > 0? a: a + y;
108        b -= q*v;
109      }
110    }
111  }
112}