Factorial Factors

March 28, 2006 at 5:29 pm | Posted in ACM Contest, Code Samples | 15 Comments

by: Mpu Gondrong

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

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-2, dengan waktu 0:00.137 dan memory 1.116 KByte.

Sampai di sini dulu, semoga sukses.

15 Comments »

RSS feed for comments on this post. TrackBack URI

  1. om Mpu… cara no.4, yg maksa pake assembler dalam pascal kok terkesan maksa ya?πŸ™‚ Mending tetep pake pure pascal aja, sekalian bisa keliatan seberapa powerfullnya pascal dan compilernya.

    Setuju om?πŸ™‚

    -Bee-

  2. ha ha ha, akhirnya ngeblog juga ente… selamat deh..πŸ™‚

  3. salam kenal buat para senior…
    ikutan cuap2 ah..πŸ™‚

  4. tolong dong gimana cara membuat algoritma yang menanyakan function faktorial seperti contoh berikut J(n)= n+n+(n-1)+(n-1)+(n-2)+(n-2)+…+1+1 tolong ya aku uda pusing gak ketemu – ketemu thanx

  5. Tolong dong jawabannya di kirim di emailku nots_gnik@yahoo.com thanx

  6. Please gimana caranya, penting banget nih aku uda muter kepalaku ngak bisa mecahin soal itu.
    Thanx

  7. splendid….
    kok saya ga ngerti ya baca source codenya??
    emang orang bego saya

    gimana cara nyari prime number kalo angkanya melebihi longint??

    misal dari 1..2^64??

  8. gemana caranya buat search bilangan prima dalam pascal???
    tq
    tolong buat secara lengkap yha???

  9. aduh,, saya bingung nih bagaimana caranya buat bilangan prima pake C++ yee?
    tolongin yah… klo bisa ama program perkalian matriksnya yeeee… makacih ya.

  10. Thanks For ALL
    Aku masih awam pascal dan delphi
    terima kasih atas adanya website ini
    rawat terus ya bro…..

  11. aduh saya bingung nih!!! gimana caranya buat program untuk mencari hasil akar suatu bilangan dalam bentuk pascal? tolong ya!!!please. wqaktu sudah mepet benget.

  12. tolongin dong nentuin bilangan prima pake GW-BASIC gimana? please dehhh

  13. tolong donk aq bingung banget nih cara membuat program bilangan algoritma pake program pascal. please!

  14. Aduh om bigung banget ni programnya panjang tapi aku sekarang udah sedikit ngerti makasih om ya algorimanya

  15. Kl penjumlahan bilangan biner, pengcodingannya sperti apa?


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.
Entries and comments feeds.

%d bloggers like this: