Dapatkan modulo dari dua array integer 4x64bit

Berikut adalah algoritma yang mudah (dan cukup efisien) yang menghitung a % b hanya dengan menggunakan pengurangan, perkalian dengan 2, pembagian dengan 2 dan perbandingan (semuanya mudah diterapkan untuk uint256 Anda).

uint256 modulo(uint256 a, uint256 b) {
  int i = 0;
  while (b <= a) {
    b = b * 2; // watch out for overflow!
    i++;
  }
  while (i--) {
    b = b / 2;
    if (b <= a) {
      a = a - b;
    }
  }
  return a;
}

Berikut ini contohnya:

start: a = 40, b = 7
i = 1, a = 40, b = 14
i = 2, a = 40, b = 28
i = 3, a = 40, b = 56

i = 3, b = 28, a = 40 - 28 = 12
i = 2, b = 14, a = 12 (b > a so nothing happens)
i = 1, b = 7, a = 12 - 7 = 5
i = 0, so we stop and return a = 5

EDIT: Mengapa ini berhasil? Cara naif menghitung residu modulo jika sebagai berikut:

int modulo(int a, int b) {
  while (a >= b) {
    a -= b;
  }
  return a;
}

Solusi yang diusulkan menggunakan ide yang sama, namun dengan cara yang lebih efisien. Kita tahu bahwa kita akan mendapatkan pengurangan b dari a tepat k kali. Oleh karena itu kita tidak mengetahui nilai k. k dapat direpresentasikan dalam biner sebagai 2^0 * k_0 + 2^1 * k_1 + 2^2 * k_2 + .... Algoritme beralih dari nilai terbesar 2^i dan mencoba mengurangi 2^i * b. Berkat itu kami mencapai kompleksitas waktu logaritmik, bukan linier.

Penafian: Saya tidak akan menggunakan implementasi ini sebagai implementasi kriptografi nyata karena rentan terhadap serangan saluran samping (waktu eksekusi berbeda tergantung pada input).