SHARE
TWEET

Untitled

a guest Jun 20th, 2019 48 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package main
  2.  
  3. import (
  4.     "fmt"
  5.     "math/big"
  6.     "runtime"
  7. )
  8.  
  9. const increment = 1000
  10. var processors int
  11.  
  12.  
  13. func main() {
  14.     a := big.NewInt(7)
  15.     b := big.NewInt(24190)
  16.     m := big.NewInt(65537)
  17.  
  18.     processors = runtime.NumCPU()
  19.     runtime.GOMAXPROCS(processors)
  20.     fmt.Println("RESULT:", babyGiant(a, b, m))
  21. }
  22.  
  23. func modInverse(a, b *big.Int) *big.Int {
  24.     return new(big.Int).ModInverse(a, b)
  25. }
  26. func mod(a, b *big.Int) *big.Int {
  27.     return new(big.Int).Mod(a, b)
  28. }
  29. func pow(a, b *big.Int) *big.Int {
  30.     return new(big.Int).Exp(a, b, nil)
  31. }
  32. func mul(a, b *big.Int) *big.Int {
  33.     return new(big.Int).Mul(a, b)
  34. }
  35. func sub(a, b *big.Int) *big.Int {
  36.     return new(big.Int).Sub(a,b)
  37. }
  38.  
  39. func babyGiant(a, b, m *big.Int) int64 {
  40.     fmt.Println("Beginning Store Generation")
  41.     var k int64 = 1000
  42.     store := make(map[string]int64)
  43.     var i int64
  44.     previous := mod(big.NewInt(1), m)
  45.     for i = 1; i < k; i++ {
  46.         if i % 1e7 == 0 {
  47.             fmt.Println("Storage of", i, "items completed.")
  48.         }
  49.         current := mod(mul(previous, a), m)
  50.         currentString := current.String()
  51.         if _, inMap := store[currentString]; inMap {
  52.             k = i
  53.             break
  54.         }
  55.         store[currentString] = i
  56.         previous = current
  57.     }
  58.     fmt.Println("Store Generation Complete")
  59.  
  60.     var r int64 = 0 - increment
  61.     rk := big.NewInt(r * k)
  62.     receiver := make(chan int64)
  63.  
  64.     semiphoreStart := processors
  65.     semiphore := semiphoreStart
  66.     for rk.Cmp(m) <= 0 {
  67.         if semiphore > 0 {
  68.             semiphore -= 1
  69.             r += increment
  70.             go func (receiver chan int64, rGiven, k int64) {
  71.                 r := rGiven
  72.                 rk := big.NewInt(r * k)
  73.                 fmt.Println("Currently at", rGiven, "nRemaining:", sub(m, rk), "n")
  74.                 for ; r < rGiven + increment+1; r++ {
  75.                     rk = big.NewInt(r * k)
  76.                     current := mod(mul(b, modInverse(pow(a, rk), m)), m)
  77.                     currentString := current.String()
  78.                     val, inMap := store[currentString]
  79.                     if inMap {
  80.                         receiver <- (val + r*k)
  81.                     }
  82.                 }
  83.                 receiver <- -1
  84.             }(receiver, r, k)
  85.         } else {
  86.             result := <- receiver
  87.             if result != -1 {
  88.                 return result
  89.             }
  90.             semiphore += 1
  91.         }
  92.     }
  93.     for ; semiphore < semiphoreStart; semiphore++ {
  94.         if result := <- receiver; result != -1 {
  95.             return result
  96.         }
  97.     }
  98.     return -1
  99. }
  100.      
  101. go func(receiver chan int64, rGiven, k int64) {
  102.             r := rGiven
  103.             ark := pow(a, big.NewInt(r*k))
  104.             ak := pow(a, big.NewInt(k))
  105.             // fmt.Println("Currently at", rGiven, "nRemaining:", sub(m, rk), "n")
  106.             for ; r < rGiven+increment+1; r++ {
  107.                 current := mod(mul(b, modInverse(ark, m)), m)
  108.                 currentString := current.String()
  109.                 val, inMap := store[currentString]
  110.                 if inMap {
  111.                     receiver <- (val + r*k)
  112.                 }
  113.                 ark.Mul(ark, ak) // a^(rk) * a^(k) = a^((r+1)k)
  114.             }
  115.             receiver <- -1
  116.         }(receiver, r, k)
  117.      
  118. package main
  119.  
  120. import (
  121.     "math/big"
  122.     "runtime"
  123.     "testing"
  124. )
  125.  
  126. func BenchmarkBabyGiant(b *testing.B) {
  127.     processors = runtime.NumCPU()
  128.     runtime.GOMAXPROCS(processors)
  129.  
  130.     b.ResetTimer()
  131.     b.ReportAllocs()
  132.  
  133.     for i := 0; i < b.N; i++ {
  134.         a := big.NewInt(7)
  135.         b := big.NewInt(24190)
  136.         m := big.NewInt(65537)
  137.  
  138.         babyGiant(a, b, m)
  139.     }
  140. }
  141.      
  142. Before:
  143. BenchmarkBabyGiant-8          50     663145338 ns/op    812469942 B/op    213165 allocs/op
  144.  
  145. After:
  146. BenchmarkBabyGiant-8         100     335030538 ns/op    425100448 B/op     85983 allocs/op
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top