Perbandingan Kinerja Metode Karatsuba dan Fast Fourier Transform Pada Persoalan Barisan Bilangan Kompleks: Studi Kasus SPOJ 11723 Help Abhishek Version-II

Riskynanda, Achmad Nashruddin (2024) Perbandingan Kinerja Metode Karatsuba dan Fast Fourier Transform Pada Persoalan Barisan Bilangan Kompleks: Studi Kasus SPOJ 11723 Help Abhishek Version-II. Other thesis, Institut Teknologi Sepuluh Nopember.

Text 5025201021-Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only until 1 October 2026. Download (4MB) | Request a copy

Abstract

Abhishek memiliki sebuah deret perkalian bilangan yang terdefinisi sehingga dibutuhkan analisis mendalam untuk mentransformasikan bentuk deret tersebut menjadi bentuk yang lebih sederhana. Deret perkalian bilangan tersebut dapat direpresentasikan dengan notasi matematis menggunakan akar persatuan kompleks yang berkaitan erat dengan transformasi Fourier. Transformasi Fourier adalah teknik matematika yang digunakan dalam analisis fungsi dalam domain frekuensi. Root of unity, sebagai akar persatuan kompleks memiliki sifat khusus yang memungkinkan bentuk deret yang ditransformasikan menjadi fungsi yang lebih sederhana. Tugas akhir ini membahas mengenai permasalahan operasi bilangan bulat yang sangat besar sehingga diperlukan metode khusus untuk menanganinya karena di luar kemampuan tipe data yang dimiliki oleh bahasa pemrograman terutama dalam menangani perkalian dua bilangan besar. Seiring dengan besarnya bilangan bulat, proses perkalian menjadi permasalahan yang erat kaitannya dengan kompleksitas waktu. Oleh karena itu pada tugas akhir ini dilakukan penerapan perkalian bilangan bulat besar menggunakan metode Karatsuba dan Fast Fourier Transform untuk mempercepat proses perkalian dua bilangan bulat besar yang direpresentasikan dalam deret polinomial bilangan basis. Berdasarkan hasil uji coba yang telah dilakukan pada studi kasus yang diberikan, solusi pendekatan metode Karatsuba mampu menyelesaikan persoalan dengan waktu minimum 0,13 detik, sedangkan metode Fast Fourier Transform dengan basis yang dinaikkan mampu memperoleh peringkat ketiga dalam segi waktu dengan catatan terbaik pada waktu 0,05 detik di laman peringkat Sphere Online Judge dengan penggunaan memori berada pada rentang 5,1 MB hingga 5,2 MB.
=================================================================================================================================
Abhishek has a series of number multiplications that is defined in such a way that it requires deep analysis to transform the form of the series into a simpler form. This series of number multiplications can be represented mathematically using complex roots of unity, which are closely related to Fourier transforms. The Fourier transform is a mathematical technique used in the analysis of functions in the frequency domain. Roots of unity, as complex roots of unity, have special properties that allow the transformed series to become a simpler function.
This final project discusses the problem of very large integer operations, requiring special methods to handle them, as they exceed the capability of data types provided by programming languages, especially in handling the multiplication of two large numbers. As the integers become larger, the multiplication process becomes a problem closely related to time complexity. Therefore, in this final project, the multiplication of large integers is carried out using the Karatsuba method and the Fast Fourier transform to speed up the process of multiplying two large integers represented in polynomial series of base numbers. Based on the tests conducted on the given case study, the Karatsuba method approach was able to solve the problem with a minimum time of 0.13 seconds, while the Fast Fourier transform method with the raised base achieved third place in terms of time with a best record of 0.05 seconds on the Sphere Online Judge ranking page, with memory usage ranging from 5.1 MB to 5.2 MB.

Item Type:	Thesis (Other)
Uncontrolled Keywords:	Bilangan Bulat Besar, Karatsuba, Fast Fourier Transform, Big Integer
Subjects:	Q Science > QA Mathematics > QA141 Numeracy--Problems, exercises, etc. Q Science > QA Mathematics > QA401 Mathematical models. Q Science > QA Mathematics > QA9.58 Algorithms
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	ACHMAD NASHRUDDIN RISKYNANDA
Date Deposited:	26 Jul 2024 05:51
Last Modified:	26 Jul 2024 05:51
URI:	http://repository.its.ac.id/id/eprint/109065

Actions (login required)

View Item