Factorial Factors

Pada kesempatan kali ini kita akan membahas soal ACM vol 8 no. 884 yaitu Factorial Factors. Tujuan dari soal ini adalah kita mencari berapakah jumlah maksimal faktor pembentuk dari angka yang ditentukan.

Dari ilustrasi pada soal:

8! = 1 . 2 . 3 . 4 . 5 . 6 . 7 . 8 
   = 2 . 3 . 2 . 2 . 5 . 3 . 2 . 7 . 2 . 2 . 2 
   = jumlah 11.

Soal ini cukup menarik karena rentang waktu hasil program cukup bervariasi dan cakupan angka yang terlibat cukup besar (1 juta). Bila penghitungan waktu terlalu rapat, atau bahkan 0:00:00, kontes menjadi tidak menarik karena siapa yang mengerjakan duluan maka dialah yang menempati peringkat atas.

Awalnya

Lewat oret-oretan sederhana di kertas, kita mendapatkan suatu pola, yaitu dari suatu bilangan kita bagi saja bilangan tersebut dengan bil prima hingga tidak bisa dibagi lagi alias berakhir dgn bil prima. Jumlah banyaknya pembagian itu adalah jumlah maksimal faktor pembentuk angka tersebut. Misal:

120 = 120:(2) = 60:(2) = 30:(2) = 15:(3) = (5)
    = 2 x 2 x 2 x 3 x 5
    = jumlah 5.
Oke, tugas berikutnya berarti kita hanya perlu mencari daftar bilangan prima (sebagai faktor pembagi) dan menghitung tiap kali terjadi pembagian. Apakah daftar bilangan ini kita simpan di array atau cari saja sambil jalan ? Kita coba menghitung sambil jalan saja. Sedikit optimasi mencari bilangan prima:
  • Lompati angka genap
  • Batasi bilangan pembagi hingga akar bilangan yang dicari
  • Pada prosesor Intel, hasil pembagian dan sisa hanya butuh 1 instruksi

Dengan modal 3 hal di atas mulailah kita mengetik. Tik, tik, tik, cring, jdut, jdar, selesai, dengan hasil sebagai seperti di bawah. Kompiler menggunakan FreePascal dengan mode kompatibel dengan Delphi. Program dijalankan di prosesor Pentium III.

program permut_primb;
{$ASMMODE INTEL}

function Faktorial(Max: Integer): Integer;
var
  I, J, K, L, M: Integer;
begin
  Result := 0;
  for I := 2 to Max do begin
    K := I;
    while not Odd(K) do begin
      K := K div 2;
      Inc(Result);
    end;
    while K > 1 do begin
      J := 3;
      while J do begin
        L := 3;
        M := Trunc(Sqrt(J));
        while (L and (J mod L > 0) do
          Inc(L, 2);
        if (L > M) then begin
          while (K mod J = 0) do begin
            asm mov K, eax end;
            Inc(Result);
          end;
        end;
        Inc(J, 2);
      end;
    end;
  end;
end;

var
  Angka: Integer;
begin
  while not EoF(Input) do begin
    Readln(Angka);
    Writeln(Faktorial(Angka));
  end;
end.

Nah, mari kita ujikan dengan angka-angka contoh pada soal. Untuk angka 2, 1996, 5 dan 8 hasil didapat dengan benar dan cepat. Namun untuk 123456 dan 1000000 mulailah terdapat keraguan, prosesnya luar biasa lama, melewati batas 10 detik yang diijinkan.

Apa yang salah ?

Tanpa pendalaman lebih lanjut, perbaikan berikutnya adalah:

  • Menyimpan dahulu bilangan prima yang ditemukan dalam array, dengan tujuan tidak mencari ulang.
  • Mencari terlebih dahulu bilangan prima, disimpan dalam konstanta array. Namun batas maksimal 10 KB upload source program dengan cepat membatasi hal ini.
  • Trik lain memperkecil source program, dengan mengompress konstanta dan program, juga tidak membantu.
  • Gabungan teknik hashing (dalam artian cukup angka-angka tertentu yang diambil sebagai titik loncat) dan compressing konstanta hingga program menjadi lebih kecil, tetap tidak berhasil.

Jalan mulai tampak buntu. Untunglah kita punya Google, teman terbaik setiap masalah. Hasil membolak-balik halaman Google berujung pada Sieve of Eratosthenes. Algoritma sederhana ini ternyata sangat ampuh untuk memecahkan persoalan kita, tinggal dikembangkan agar sesuai untuk pencarian faktorial.

Bila kita ikuti algoritma tersebut, untuk bilangan dari 2 s/d 15, pertama-tama array kita inisialisasi dengan 0.

array:  2 3 4 5 6 7 8 9 10 11 12 13 14 15
nilai:  0 0 0 0 0 0 0 0  0  0  0  0  0  0

Bila setiap array bilangan dan kelipatannya kita tambahkan 1, misalnya 2, 4, 6, 8, 10, 12, 14, lalu 3, 6, 9, 12, 15, selanjutnya 5, 10, 15, dan seterusnya, maka kita dapatkan hasil berikut.

array:  2 3 4 5 6 7 8 9 10 11 12 13 14 15
nilai:  1 1 1 1 2 1 1 1  2  1  2  1  2  2

Kita sudah mendapatkan sejumlah faktorial yang kita perlukan. Setiap array yang bernilai 1 berarti itu adalah bilangan prima. Untuk angka 6 maka berjumlah 2, yaitu 2 x 3. Namun masih ada kekurangan, misal angka 4 yang di sini bernilai 1, seharusnya 2 (2 x 2), atau 8 yang harusnya 3 (2 x 2 x 2). Kekurangan ini mudah saja kita perbaiki, yaitu setiap pangkat dari bilangan juga kita tambahkan dengan 1. Jadi untuk 2 (+0), 4 (+2), 8 (+3), lalu 3 (+0), 9 (+1), dan seterusnya.

array:  2 3 4 5 6 7 8 9 10 11 12 13 14 15
nilai:  1 1 2 1 2 1 3 2  2  1  2  1  2  2

Kini daftar faktorial kita sudah komplit. Namun karena yang diminta adalah jumlah angka tersebut, misalnya untuk 5 jumlahnya 11 (1 + 1 + 2 + 1), maka kita perlukan juga array untuk menampung hasil penjumlahan tersebut untuk mempercepat pencarian. Optimasi program yang bisa kita lakukan adalah melompati setiap bilangan genap, selain menghemat proses juga untuk menghemat memory. Untuk mengembalikan angka cukup menggeser ke kanan (shr) untuk membagi 2 atau menggeser ke kiri (shl, tapi cukup dengan operator perkalian) untuk mengali 2.

array:  3 5 7 9 11 13 15
nilai:  1 1 1 2  1  1  2

Untuk mendapatkan faktor pada angka genap yaitu dengan membagi 2 angka tersebut hingga didapat angka ganjil yang kemudian dicari faktornya pada array. Misalnya 36 bisa kita jabarkan menjadi 2 x 2 x 9 = 1 + 1 + 2 = 4.

Berikut program kita sejauh ini, yang bila dijalankan pada Pentium III waktu proses untuk mencari 1000000 jumlah faktorial kurang dari 1 detik.

program permut_primh;

const
  MaksAngka = 1000000;
  MaksAkar  = 1000;

var
  Faktor: array[0..MaksAngka div 2] of Byte;
  Hasil: array[0..MaksAngka] of Integer;

procedure CariPrima;
var
  I, J, K, H: Integer;
begin
  J := 3; H := 1;
  Hasil[2] := 1;
  while J do begin
    if Faktor[J shr 1] = 0 then begin
      K := J;
      repeat
        Inc(Faktor[K shr 1]);
        Inc(K, J * 2);
      until K > MaksAngka;
      // tambahkan pangkat kelipatan x -
      if J then begin
        K := J * J;
        while K do begin
          I := K;
          repeat
            Inc(Faktor[I shr 1]);
            Inc(I, K * 2);
          until I > MaksAngka;
          K := K * J;
        end;
      end;
    end;
    Inc(H, Faktor[J shr 1]);
    Hasil[J] := H;
    // untuk bil genap -
    Inc(J);
    K := J; I := 0;
    while K and 1 = 0 do begin
      Inc(I);
      K := K shr 1;
    end;
    Inc(H, Faktor[K shr 1] + I);
    Hasil[J] := H;
    Inc(J);
  end;
end;

var
  I: Integer;
begin
  CariPrima;
  repeat
    Readln(I);
    Writeln(Hasil[I]);
  until I = 0;
end.

Catatan lain soal optimasi, karena kita bermain dengan angka dan memory yang besar maka efisiensi dari sisi memory itu hasilnya sangat signifikan. Dengan menghilangkan bilangan genap, kita memperoleh perbedaan cukup berarti. Perlu diingat bahwa dengan mendayagunakan memory komputer yang supercepat, seperti cache level 1 dan 2, hasilnya akan sangat mencolok.

Lebih Lanjut

Optimasi lebih lanjut program di atas yaitu:

  • Menekan array faktor hingga separuhnya, mengingat faktor angka hingga 1000000 tidak lebih dari 16, sehingga 1 byte bisa untuk 2 angka (high dan low).
  • Menekan array hasil hingga cukup bilangan ganjil yang disimpan, sedangkan angka genap dapat dicari melalui bilangan ganjil terdekat + faktor bilangan genap tersebut.
  • Menghemat kembali array hasil dengan hanya menyimpan selisih tiap-tiap angka (hingga batas byte atau 256) dan menyimpan nilai lengkapnya dalam interval tertentu.
  • Menulis ulang dalam bahasa C dan dikompilasi dengan GCC, untuk kemudian diambil versi assemblynya yang sudah optimized, dan dibungkus sedemikian rupa hingga dapat dikompilasi oleh FreePascal.
  • Menggantikan fungsi-fungsi Input / Output built-in dari FreePascal dengan fungsi-fungsi sendiri yang lebih baik.
  • Mengganti algoritma Sieve of Eratosthenes dengan Sieve of Atkin yang lebih modern.

Selanjutnya 6 tahap optimasi ini merupakan Pekerjaan Rumah bagi pembaca yang budiman, bila ingin hasil yang maksimal. Hasil untuk tahap 1 s/d 5 yang sudah saya kerjakan, hasilnya adalah urutan ke-3, dengan waktu 0.044 dan memory 1.116 KByte.

Sampai di sini dulu, semoga sukses.

1 Komentar »

  1. ismail said

    Aku mau input angka di aplikasi lazarus..misalnya aku ketik 100000
    di aplikasi nya ke format otomatis nyesuain ke 100.000 gimana cara setting nya ya ???

RSS feed for comments on this post

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s