daily pastebin goal
44%
SHARE
TWEET

Untitled

a guest Feb 20th, 2019 91 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.*
  2.  
  3. fun mark_sieve(arr: BooleanArray, _first: Int, last: Int, factor: Int) {
  4.     var first = _first;
  5.  
  6.     arr[first] = false
  7.  
  8.     while( last-first > factor ) {
  9.         first += factor
  10.         arr[first] = false;
  11.     }
  12. }
  13.  
  14.  
  15. // 걸러내기 위한 인덱스들을 47페이지(한글판) 규칙에 따라 정리한 코드
  16. fun sift0(first: Int, n: Int):BooleanArray {
  17.     // n 크기 배열 생성 후 초기화
  18.     var arr = BooleanArray(n)
  19.     arr.fill(true)
  20.  
  21.     var i = 0
  22.     var index_square = 3
  23.  
  24.     while (index_square < n) {
  25.         // 고정: index_square = 2*i^2 + 6*i + 3
  26.         if (arr[first+i]) {
  27.             // this means arr[i] is a prime
  28.             mark_sieve(arr, first + index_square, first + n, i + i + 3)
  29.         }
  30.         ++i
  31.         index_square = 2*i*(i + 3) + 3
  32.     }
  33.  
  34.     return arr
  35. }
  36.  
  37. // 루프 안에서 mark_sieve를 호출 시 계산해야 하는 값들을 빼냄
  38. fun sift1(first: Int, n: Int):BooleanArray {
  39.     // n 크기 배열 생성 후 초기화
  40.     var arr = BooleanArray(n)
  41.     arr.fill(true)
  42.  
  43.     val last = first + n
  44.     var i = 0
  45.     var index_square = 3
  46.     var factor = 3
  47.  
  48.     while (index_square < n) {
  49.         // 고정: index_square = 2*i^2 + 6*i + 3
  50.         // 고정: factor = 2i + 3
  51.         if (arr[first+i]) {
  52.             // this means arr[i] is a prime
  53.             mark_sieve(arr, first + index_square, last, factor )
  54.         }
  55.         ++i
  56.         factor = i + i + 3
  57.         index_square = 2*i*(i + 3) + 3
  58.     }
  59.  
  60.     return arr
  61. }
  62.  
  63.  
  64. // 우선순위 줄임(strength reduction) 기법을 통해 덜 비싼 연산을 사용하는 동등한 코드로 치환
  65. // delta_factor = 2              : factor(i)는 초기값에서 시작해 2씩 증가하는 등차수열
  66. // delta_index_square = factor(i) + factor(i+1)  : index_square는 factor(i)와 factor(i+1)을 더한 값
  67. //
  68. // 여기서 factor(i)는 이미 알고 있고(루프에서 새 factor를 계산하기 직전 값), factor(i+1)은 이번 루프에서 계산하면 된다.
  69. fun sift2(first: Int, n: Int):BooleanArray {
  70.     // n 크기 배열 생성 후 초기화
  71.     var arr = BooleanArray(n)
  72.     arr.fill(true)
  73.  
  74.     val last = first + n
  75.     var i = 0
  76.     var index_square = 3
  77.     var factor = 3
  78.  
  79.     while (index_square < n) {
  80.         // 고정: index_square = 2*i^2 + 6*i + 3
  81.         // 고정: factor = 2i + 3
  82.         if (arr[first+i]) {
  83.             // this means arr[i] is a prime
  84.             mark_sieve(arr, first + index_square, last, factor )
  85.         }
  86.         ++i
  87.         index_square += factor        // factor를 계산하기 전에 index_square에 더해서 factor(i)를 추가
  88.         factor += 2
  89.         index_square += factor        // factor를 계산했으므로 현재 factor는 factor(i+1)을 저장하고 있음. 이를 index_square에 추가
  90.     }
  91.     return arr
  92. }
  93.  
  94. fun testSameResults() {
  95.     val arr0 = sift0(0, 100001)
  96.     var arr1 = sift1(0, 100001)
  97.     var arr2 = sift2(0, 100001)
  98.  
  99.     assert(Arrays.compare(arr0, arr1) == 0)
  100.     assert(Arrays.compare(arr1, arr2) == 0)
  101.     assert(Arrays.compare(arr2, arr0) == 0)
  102. }
  103.  
  104. fun benchmark() {
  105.     var sum1 = 0L
  106.     var sum2 = 0L
  107.     var sum3 = 0L
  108.     (1..20).forEach {
  109.         var t3 = System.nanoTime()
  110.         sift0(0, 100000000)
  111.         var t4 = System.nanoTime()
  112.         sift1(0, 100000000)
  113.         var t5 = System.nanoTime()
  114.         sift2(0, 100000000)
  115.         var t6 = System.nanoTime()
  116.  
  117.         sum1 += (t4 - t3)
  118.         sum2 += (t5 - t4)
  119.         sum3 += (t6 - t5)
  120.         println("sift0: ${t4 - t3}")
  121.         println("sift1: ${t5 - t4}")
  122.         println("sift2: ${t6 - t5}")
  123.     }
  124.  
  125.     println("average sift0 : ${sum1 / 20.0}")
  126.     println("average sift1 : ${sum2 / 20.0}")
  127.     println("average sift2 : ${sum3 / 20.0}")
  128. }
  129.  
  130. // 내 컴퓨터에서(맥북프로 2017) : 단위 나노초
  131. //
  132. // average sift0 : 8.470951253E8
  133. // average sift1 : 8.4314250685E8
  134. // average sift2 : 8.4427361505E8/
  135. //
  136.  
  137. var arr107 = sift2(0,107)
  138.  
  139. println(
  140.     arr107.mapIndexed{i, b -> Pair(i*2+3, b)}
  141.     .filter{it.second}
  142.     .map{it.first}
  143.     .joinToString(prefix="{ ", postfix = " }"))
  144.  
  145. // arr107에 있는 불린 데이터를 가지고
  146. // (소수, 누적 소수 개수)로 이뤄진 컬렉션을 만든다
  147. // 체를 걸러서 남은 소수 리스트에서 소수 누적 개수는 인덱스에 2를 더해야 한다.
  148. // (짝수 소수 2가 리스트에서 빠져있고, 0번이 첫번째 홀수 소수이므로 누적은 2부터 시작이다)
  149. var coords = arr107.mapIndexed{i, b -> Pair(i*2+3, b)}
  150.     .filter{it.second}
  151.     .map{it.first}
  152.     .mapIndexed { index, i -> Pair(i, index+2) }
  153.  
  154. // 맨 앞에 짝수 소수인 2를 추가해준다
  155. val all = listOf(Pair(2,1))+coords.toList()
  156.  
  157. // 그래프를 엑셀에서 쉽게 그리기 위해 소수와 소수 사이의 빈 (수, 누적개수) 쌍들을 채워넣어준다
  158. // 일단 windowed(2)를 해서 인접한 두 (소수, 누적개수)의 쌍을 찾고,
  159. // 인접 두 소수 사이의 수를 코틀린 .. (범위를 만들어내는 연산자)를 사용해 만들어내서 (수, 누적개수) 쌍 리스트를 만든다
  160. // 이를 flatMap으로 펼쳐서 빈 정수 값이 없는 누적 분포를 만들어낸다
  161. val full = all.windowed(2).flatMap {
  162.     (first, second) -> (first.first .. (second.first-1)).map { Pair(it, first.second) }
  163. }
  164.  
  165. // 엑셀에 사용하기 위해 ,로 분리하고 한 줄에 한 쌍만 표시한다
  166. println(full.joinToString(separator = "\n", transform = { "${it.first}, ${it.second}" }))
  167.  
  168. fun gcm(a:Int, b:Int): Int =
  169.     if(a==b) b
  170.     else if(a > b) gcm(a-b, b)
  171.     else /*if(a<b)*/ gcm(a, b-a)
  172.  
  173. println("gcm(196,42) = ${gcm(196,42)}")
  174. println("gcm(154,42) = ${gcm(154,42)}")
  175. println("gcm(112,42) = ${gcm(112,42)}")
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