+/EE360P
distributed systems
git clone https://git.julia.blue/+/EE360P
07ca65d
master
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 { 22static final long MAX_SQRT_LONG = (long )Math .sqrt (Long .MAX_VALUE ); 23 24/** Compute 2^e mod n */ 25public static long mod (long e ,long n ) { 26final int HALF = (63 -Long .numberOfLeadingZeros (n )) >>1 ; 27final int FULL =HALF <<1 ; 28final long ONES = (1 <<HALF ) -1 ; 29 30long r =2 ; 31for (long mask =Long .highestOneBit (e ) >>1 ;mask >0 ;mask >>=1 ) { 32if (r <=MAX_SQRT_LONG ) { 33r *=r ; 34if (r >=n )r %=n ; 35 }else { 36// r^2 will overflow 37final long high =r >>>HALF ; 38final long low =r &=ONES ; 39 40r *=r ; 41if (r >=n )r %=n ; 42 43if (high !=0 ) { 44long s =high *high ; 45if (s >=n )s %=n ; 46for (int i =0 ;i <FULL ;i ++) 47if ((s <<=1 ) >=n )s -=n ; 48 49if (low ==0 ) 50r =s ; 51else { 52long t =high *low ; 53if (t >=n )t %=n ; 54for (int i = -1 ;i <HALF ;i ++) 55if ((t <<=1 ) >=n )t -=n ; 56 57r +=s ; 58if (r >=n )r -=n ; 59r +=t ; 60if (r >=n )r -=n ; 61 } 62 } 63 } 64 65if ((e &mask ) !=0 ) { 66r <<=1 ; 67if (r >=n )r -=n ; 68 } 69 } 70return r ; 71 } 72 73/** Given x in [0,1) and a in (-1,1), 74* return (x, a) mod 1.0. 75*/ 76public static double addMod (double x ,final double a ) { 77x +=a ; 78return x >=1 ?x -1 :x <0 ?x +1 :x ; 79 } 80 81/** Given 0 < x < y, 82* return x^(-1) mod y. 83*/ 84public static long modInverse (final long x ,final long y ) { 85if (x ==1 )return 1 ; 86 87long a =1 ; 88long b =0 ; 89long c =x ; 90 91long u =0 ; 92long v =1 ; 93long w =y ; 94 95for (;;) { 96 { 97final long q =w /c ; 98w -=q *c ; 99u -=q *a ; 100if (w ==1 )return u >0 ?u :u +y ; 101v -=q *b ; 102 } 103 { 104final long q =c /w ; 105c -=q *w ; 106a -=q *u ; 107if (c ==1 )return a >0 ?a :a +y ; 108b -=q *v ; 109 } 110 } 111 } 112}