Penyelesaian Kasus SPOJ 35582: Fibonacci Power Sum (Hard) dengan Metode Transformasi Linear dan Nilai Eigen

Gita, Kartika Diva Asmara (2025) Penyelesaian Kasus SPOJ 35582: Fibonacci Power Sum (Hard) dengan Metode Transformasi Linear dan Nilai Eigen. Other thesis, Institut Teknologi Sepuluh Nopember.

Text 5025211039-Undergraduate_Thesis.pdf Restricted to Registered users only Download (7MB) | Request a copy

Abstract

Deret Fibonacci merupakan salah satu deret bilangan penting dengan berbagai aplikasi, terutama dalam bidang komputasi dan kriptografi. Salah satu contoh permasalahannya, yaitu jumlahan perpangkatan bilangan Fibonacci, seringkali menantang efisiensi komputasi. Tugas akhir ini berfokus pada penyelesaian kasus SPOJ 35582 – Fibonacci Power Sum (Hard Version), yang memerlukan pendekatan algoritmik optimal untuk menangani input berskala besar, yakni dengan nilai N dan C hingga 10^18 serta K hingga 10^5. Tugas akhir ini berhasil mengatasi tantangan tersebut menggunakan konsep transformasi linear dan nilai eigen. Pendekatan dimulai dari analisis relasi rekurens deret Fibonacci untuk ikontruksikan dalam bentuk matriks Fibonacci. Melalui diagonalisasi pada eksponensiasi matriks berbasis nilai eigen, diperoleh solusi tertutup dengan kompleksitas waktu O(log n). Untuk perpangkatan bilangan Fibonacci, digunakan ekspansi binomial bentuk a+b√5 kemudian dihitung dengan rumus deret geometri. Proses komputasi diperkuat dengan eksponensiasi modular cepat dan Teorema Euler untuk mengoptimalkan aritmetika modulo bilangan prima.Pendekatan yang dirancang dalam tugas akhir ini terbukti berhasil menyelesaikan permasalahan dan diterima oleh sistem online judge. Algoritma yang dikembangkan menghasilkan waktu rata-rata 4,65 detik dari batas 20 detik dan konsumsi memori 5,2 MB dari batas 1536MB dalam sepuluh kali pengujian. Temuan ini menunjukkan potensi besar penerapan metode aljabar linear dalam meningkatkan efisiensi komputasi Fibonacci skala besar.
======================================================================================================================================
The Fibonacci sequence is a fundamental number series with diverse applications, particularly in computation and cryptography. However, calculating the sum of Fibonacci numbers raised to a power often poses significant computational efficiency challenges. This final project focuses on solving the SPOJ 35582 – Fibonacci Power Sum (Hard Version) problem, which requires an optimal algorithmic approach to handle large-scale input, with values of N and C reaching up to 10^18, and K up to 10^5.
This research successfully addresses the challenge using the concepts of linear transformation and eigenvalues. The approach begins with analyzing the recurrence relation of the Fibonacci sequence, which is then constructed into a Fibonacci matrix form. Through matrix exponentiation via diagonalization based on eigenvalues, a closed-form solution is obtained with time complexity of O(log n). For handling the exponentiation of Fibonacci numbers, a binomial expansion of the form a+b√5 is employed, with the results then calculated using the geometric series formula. The computational process is further enhanced by fast modular exponentiation and Euler's Totient Theorem to optimize modular arithmetic operations on prime numbers.
The designed approach in this final project successfully solves the problem and was accepted by the online judge system. The developed algorithm achieved an average execution time of 4.65 seconds out of a 20-second time limit, and memory usage of 5.2 MB out of the 1536 MB limit across ten test cases. These findings highlight the significant potential of applying linear algebra methods to enhance the efficiency of large-scale Fibonacci computations.

Item Type:	Thesis (Other)
Uncontrolled Keywords:	binomial expansion, closed-form solution, fast modular exponentiation, fibonacci, geometric series, linear transformation, matrix exponentiation, deret geometri, ekspansi binomial, eksponensiasi matriks, eksponensiasi modular cepat, fibonacci, solusi bentuk tertutup, transformasi linear
Subjects:	Q Science > QA Mathematics > QA141 Numeracy--Problems, exercises, etc. Q Science > QA Mathematics > QA184 Algebra, Linear Q Science > QA Mathematics > QA9.58 Algorithms
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	Kartika Diva Asmara Gita
Date Deposited:	29 Jul 2025 09:55
Last Modified:	29 Jul 2025 09:55
URI:	http://repository.its.ac.id/id/eprint/122715

Actions (login required)

View Item