Aritmetički i algebarski algoritmi -- seminarske teme

Zadnja promjena: 27.12.2007. u 16:31.

Kako se bira tema?

• Izbor teme ide po sistemu: tko se prvi (pri)javi, njegova je!
• Realizacija prijava, u načelu, ide preko foruma za kolegij (link je malo niže).
• Prije izbora teme, prvo pogledajte na forum koje teme su već izabrane. To je jedini mjerodavni popis!
• Na ovom popisu povremeno će se ``brisati'' linkovi na već izabrane teme.

Link na forum za kolegij za pregled izabranih tema i prijavu.

Upozorenje: dobar dio članaka je velik, pa on-line pregled i download može dugo trajati.

• Ovdje je cijela arhiva (zip, 95.5 MB) svih tema s originalnim popisom.

Popis tema (u nekim blokovima)

Jednostavni algoritmi:

1. A New Algorithm for Inner Product (pdf, 875 kB)

Pretvaranje iz baze u bazu:

2. High-Speed Binary-to-Decimal Conversion (pdf, 800 kB)

Verižni razlomci:

3. Application of Continued Fractions for Fast Evaluation of Certain Functions on a Digital Computer (pdf, 2503 kB)
4. On the Use of Continued Fractions for Digital Computer Arithmetic (pdf, 759 kB)
5. A Method for Solving Polynomial Equations by Continued Fractions (pdf, 752 kB)

Dijeljenje:

6. Generation of Products and Quotients Using Approximate Binary Logarithms for Digital Filtering Applications (pdf, 1777 kB)
7. An Augmented Iterative Array for High-Speed Binary Division (pdf, 2108 kB)
8. Integer Division Using Reciprocals (pdf, 421 kB)
9. On-Line Algorithms for Division and Multiplication (pdf, 2319 kB)
10. The Correspondence Between Methods of Digital Division and Multiplier Recoding Procedures (pdf, 1888 kB)
11. On Division by Functional Iteration (pdf, 866 kB)
12. Higher-Radix Division Using Estimates of the Divisor and Partial Remainders (pdf, 1704 kB)
13. A Polynomial-Based Division Algorithm (pdf, 427 kB)

Dijeljenje (nastavak):

14. Multiprecision Integer Division Examples Using Arbitrary Radix (pdf, 168 kB)
15. An Overrelaxation for a Numerical Inverse of a Constant (pdf, 710 kB)
16. Speeding up an Overrelaxation Method of Division in Radix-2^n Machine (pdf, 496 kB)

Dijeljenje (još malo):

17. On Range-Transformation Techniques for Division (pdf, 921 kB)
18. On Optimal Iterative Schemes for High-Speed Division (pdf, 832 kB)
19. A Division Algorithm for Signed-Digit Arithmetic (pdf, 638 kB)

Euklidov algoritam:

20. Analysis of fast versions of the Euclid Algorithm (pdf, 301 kB)

Brza Fourierova transformacija:

21. Fast Computational Algorithms for Bit Reversal (pdf, 3227 kB)
22. A Generalization of the Fast Fourier Transform (pdf, 1951 kB)
23. A New Hybrid Algorithm for Computing a Fast Discrete Fourier Transform (pdf, 3242 kB)
24. Fourier Transform Computers Using CORDIC Iterations (pdf, 2838 kB)
25. An Algorithm for the Machine Computation of Partial-Fractions Expansion of Functions Having Multiple Poles (pdf, 806 kB)

Elementarne funkcije u floating-pointu:

26. Parallel Multiplicative Algorithms for Some Elementary Functions (pdf, 766 kB)
27. More Efficient Radix-2 Algorithms for Some Elementary Functions (pdf, 2108 kB)
28. High-Speed Double-Precision Computation of Reciprocal, Division, Square Root, and Inverse Square Root (pdf, 731 kB)
29. Economic Pseudodivision Processes for Obtaining Square Root, Logarithm, and Arctan (pdf, 784 kB)
30. A Digit-by-Digit Algorithm for m-th Root Extraction (pdf, 624 kB)

Euklidska norma vektora u floating-pointu:

31. Programming Pearls - Birth of a Cruncher (Euclidean distance) (pdf, 670 kB)
32. A Portable Fortran Program To Find the Euclidean Norm of a Vector (pdf, 447 kB)

Zaokruživanje u floating-pointu:

33. A Comparison of Three Rounding Algorithms for IEEE Floating-Point Multiplication (pdf, 351 kB)
34. Analysis of Rounding Methods in Floating-Point Arithmetic (pdf, 2666 kB)

Množenje:

35. Uniform Shift Multiplication Algorithms Without Overflow (pdf, 680 kB)
36. The Quasi-Serial Multiplier (pdf, 2010 kB)
37. A Binary Multiplication Scheme Based on Squaring (pdf, 560 kB)
38. High-Speed Computer Multiplication Using a Multiple-Bit Decoding Algorithm (pdf, 627 kB)
39. On Binary Multiplication Using the Quarter Square Algorithm (pdf, 550 kB)
40. A Proof of the Modified Booth's Algorithm for Multiplication (pdf, 451 kB)
41. An Efficient Polynomial-Modulus Based Technique for Multiplication of Large Integers (pdf, 265 kB)

Negativne baze:

42. Arithmetic Algorithms in a Negative Base (pdf, 3182 kB)
43. Deterministic Division Algorithm in a Negative Base (pdf, 1794 kB)
44. Complementary Two-Way Algorithms for Negative Radix Conversions (pdf, 1205 kB)
45. Divide-and-Correct Algorithm for Division in a Negative Base (pdf, 398 kB)
46. Arithmetic Algorithms in a Negative Base (pdf, 551 kB)

Složenost operacija:

47. Hardware Complexity of Modular Multiplication and Exponentiation (pdf, 4498 kB)

Numeričke aproksimacije funkcija:

48. Optimal Piecewise Polynomial L_2 Approximation of Functions of One and Two Variables (pdf, 791 kB)
49. A Piecewise Linear Approximation of log_2 x with Equal Maximum Errors in All Intervals (pdf, 1660 kB)

Generiranje pseudoslučajnih brojeva:

50. A More Portable Fortran Random Number Generator (pdf, 341 kB)

Aritmetika u sustavima ostataka:

51. Sign Detection in Residue Number Systems (pdf, 1205 kB)

Simetrični sustavi ostataka:

52. Floating-Point Arithmetic Algorithms in the Symmetric Residue Number System (pdf, 3668 kB)
53. General Division in the Symmetric Residue Number System (pdf, 3406 kB)

Nije primjereno, ali ako netko baš želi:

54. On the Parallel Evaluation of Polynomials (pdf, 715 kB)
55. The Relationship Between Two Fast Fourier Transforms (pdf, 1760 kB)
56. Mathematical Foundation of Computer Arithmetic (pdf, 3225 kB)
57. Floating-Point Computation of Functions with Maximum Accuracy (pdf, 3721 kB)
58. A General Hardware-Oriented Method for Evaluation of Functions and Computations in a Digital Computer (pdf, 3325 kB)
59. A Formalization of Floating-Point Numeric Base Conversion (pdf, 2867 kB)
60. Properties of the Multidimensional Generalized Discrete Fourier Transform (pdf, 3088 kB)
61. Implementation of FFT Structures Using the Residue Number System (pdf, 4820 kB)
62. Using an Efficient Sparse Minor Expansion Algorithm to Compute Polynomial Subresultants and the Greatest Common Denominator (pdf, 1732 kB)
63. Numerical Technique for the Convolution of Piecewise Polynomial Functions (pdf, 3042 kB)
64. An Algorithm for Redundant Binary Bit-Pipelined Rational Arithmetic (pdf, 1088 kB)