Algorithms for programmers - ideas and source code free download online
Title: Algorithms for programmers - ideas and source code Author(s): Joerg Arndt Pages: 980 Publisher: http://www.jjj.de/fxt/ Publication date: 2008 Language: English Format: PDF ISBN-10: ISBN-13: Description: Note: Draft version1 of 2008-July-17. The steadily growing "Algorithms for programmers" text (the fxtbook). This is the (work in progress) book "Algorithms for programmers". Publication is planned for the year 2008. Home page: http://www.jjj.de/fxt/
This is a draft of a book about selected algorithms. The audience in mind are programmers who are interested in the treated algorithms and actually want to create and understand working and reasonably optimized code.
The style varies somewhat which I do not consider bad per se: While some topics (as fast Fourier transforms) need a clear and explicit introduction others (like the bit wizardry chapter) seem to be best
presented by basically showing the code with just a few comments. The pseudo language Sprache is used when I see a clear advantage to do so, mainly when the corresponding C++ does not appear to be self explanatory. Larger pieces of code are presented in C++. C programmers do not need to be shocked by the `++' as only a rather minimal set of the C++ features is used. Some of the code, especially in part 3 (Arithmetical algorithms), is given in the pari/gp language as the use of other languages would likely bury the idea in technicalities. A printable version of this book will always stay online for free download. The referenced sources are online as part of FXT (fast transforms and low level routines [19]) and hfloat (high precision foating point algorithms [20]).
The reader is welcome to criticize and suggest improvements. Please name the draft version (date) with your feedback! This version is of 2008-July-17. Note that you can copy and paste from the PDF and DVI versions. Thanks go to those1 who helped to improve this document so far!
In case you want to cite this document, please avoid referencing individual chapters or sections as their numbers (and titles) may change.
Contents
Part I Low level algorithms p.1
1 Bit wizardry p.3
2 Permutations p.91
3 Sorting and searching p.121
4 Data structures p.147
Part II Combinatorial generation p.169
5 Conventions and considerations p.171
6 Combinations p.175
7 Compositions p.193
8 Subsets p.201
9 Mixed radix numbers p.219
10 Permutations p.233
11 Subsets and permutations of a multiset p.291
12 Gray codes for strings with restrictions p.299
13 Parenthesis strings p.317
14 Integer partitions p.331
15 Set partitions p.341
16 A string substitution engine p.357
17 Necklaces and Lyndon words p.361
18 Hadamard and conference matrices p.373
19 Searching paths in directed graphs p.381
Part III Fast orthogonal transforms p.401
20 The Fourier transform p.403
21 Algorithms for fast convolution p.437
22 The Walsh transform and its relatives p.457
23 The Haar transform p.493
24 The Hartley transform p.511
25 Number theoretic transforms (NTTs) p.535
26 Fast wavelet transforms p.543
Part IV Fast arithmetic p.549
27 Fast multiplication and exponentiation p.551
28 Root extraction p.569
29 Iterations for the inversion of a function p.591
30 The arithmetic-geometric mean (AGM) p.603
31 Logarithm and exponential function p.627
32 Numerical evaluation of power series p.641
33 Computing the elementary functions with limited resources p.655
34 Recurrences and Chebyshev polynomials p.667
35 Cyclotomic polynomials, Hypergeometric functions, and continued fractions p.687
36 Synthetic Iterations * p.723
Part V Algorithms for finite fields p.761
37 Modular arithmetic and some number theory p.763
38 Binary polynomials p.827
39 Shift registers p.869
40 Binary finite fields: GF (2n ) p.893
A The electronic version of the book p.929
B Machine used for benchmarking p.931
C The pseudo language Sprache p.933
D The pari/gp language p.935
Bibliography p.943
Part Index p.961
Algorithms for programmers - ideas and source code free download links:
Title: Algorithms for programmers - ideas and source code