Neat algorithms

[mrflibble]

Gave it a go as well for the swapping sequences, since that was a relatively small code change. Decided to go a little higher with the polynomial degrees. So for tree depth of 3 (the example graphs in this thread) I went up to degree 9 polynomials. But still no dice.

I wonder if it would be viable to "find" the polynomials by construction, and then try to simplify where possible. I'd expect there to be 21th degree polynomials that would do the trick for a mere tree depth of 3. That is way beyond what I would call an elegant solution, but it might help in gaining some insights. At least at this point I don't see a nice solution. Not that that means anything really, because I am perfectly capable of being mathematically blind as a bat.

As for summing the Fourier transform of digits, that does look suspiciously like finding prime (or co-prime) factors for both multiplicands. In that case multiplication of the original numbers boils down to adding the multiplicities of the (co-)prime factors. Similar to how you can do fast counters or multipliers in fpga by having a bunch of counters each with a prime modulo. Or coprime modulos, since for example 3*5=15 and 2^4=16 are rather convenient to map to actual hardware.

[legacy]

Absolutely; digit reversal is one of those things that surprised the heck out of me when I first encountered it.  I thought it only appeared in games and tricks, not in real-world tasks, and not in stuff related to graphs!
My intuition says the cyclic subgraphs are related to digit reversal, but my math-fu isn't good enough to be sure.

I haven't understood where the "digit reversal" is useful. Can you guys give an example 

[mrflibble]

I haven't understood where the "digit reversal" is useful. Can you guys give an example 

Maybe you managed to miss this post? 



Check out the binary representations of those nodes...

[Ice-Tea]

Am thinking of looking at turbo codes - are they nice to study?

I did my thesis on them

[mrflibble]

Am thinking of looking at turbo codes - are they nice to study?

I did my thesis on them

So is that a yes, or a no?

[Ice-Tea]

Well, yes. It was quite rewarding to get the "point". But as far as I remember, it's not exactly something to tack on in a hurry. Takes a fair amount of thinking and resources.

All that was 20 years ago with very green Ice-Tea, so my memories may be a bit colored

[coppice]

Well, yes. It was quite rewarding to get the "point". But as far as I remember, it's not exactly something to tack on in a hurry. Takes a fair amount of thinking and resources.

All that was 20 years ago with very green Ice-Tea, so my memories may be a bit colored

Pretty much any advanced coding scheme has to be planned into a comms system from the start, from simple 2D convolutional codes up to the latest stuff like polar codes.

[chris_leyson]

Talking of cyclic things and Galois fields, The fast-M transform is a quick way of cross correlating a binary M sequence or maximal length sequence using the fast Walsh–Hadamard transform. https://epubs.siam.org/doi/10.1137/0220043

[Nominal Animal]

I haven't understood where it's useful.

Let's say you x_i in ascending order with i=1..N in a list or a tree or a heap, and you want to construct a perfect binary search tree out of them.  (One example is when you fully balance a binary search tree.)  Then, k(i,N) gives you the index in an array-based binary tree, where element x_i is located at.  It turns out that even though the formula for k(i,N) looks ugly, current processors can do it faster than the amortized average latency in random memory accesses.  So, it is basically as cheap as a scatter-gather copy of the tree; you get the binary search tree construction for free.

Analogously, if you do have a perfect binary tree stored in an array, and you want to access the ith element, it is at index k(i,N).  Or, if you have an element at index k, it is i(k,N)'th in the tree; no need to backtrack to root or anything like that.

In my case, I wanted to use something I call chunked binary search trees (although I think mathematicians use partitioned instead).  The idea is that because our computers (both caches and storage media) store data in chunks (pages or segments), to efficiently locate sorted data, we store the most often used elements in the very first chunk.  Consider a binary search among N elements: every search checks the element at N/2. On average, almost half the searches check the element at 3N/4, and almost half the element at N/4.  We store these in the very first tree, so that all searches use the very first tree; almost all searches use either the second or third tree; almost all searches use the fourth, fifth, sixth, or seventh tree, and so on.  See how the probability of access is 2^1-L, where L is the level of the subtree?  We end up with a binary search tree of binary search trees, and the level of the tree directly reflects the probability of that particular tree needed for an uniformly random search.  Each tree is up to one chunk in size, and they are stored in the "storage order". (The contents of each tree can be in linear order, "in-order".)

With this scheme, the number of chunks needed to find the element with the desired value is minimized.  It is perfect for read-only memory-mapping large data sets, as you can let the kernel manage which pages of the mapping are in memory, and which will be read from storage when next needed; it will respond dynamically to memory pressure, so you'll get the maximum benefit of available memory with automatic resident set shrinking when other tasks need the RAM.

While the formulae for i(k,N) and k(i,N) look ugly, they are trivial for current (desktop and server) processors; they contain hardware instructions for the operations, and can evaluate the expressions in just a few cycles.  The main problem with this scheme is that I have not yet found an efficient enough way to describe it to other programmers; and the C code that implements it, tends to utterly confound and exasperate anyone who does not understand the underlying idea first.

[legacy]

The main problem with this scheme is that I have not yet found an efficient enough way to describe it to other programmers; and the C code that implements it, tends to utterly confound and exasperate anyone who does not understand the underlying idea first.

Yep. I have recently implemented B-tree toy-filesystem where everything that the filesystem stores is organized in B-trees.
- free inodes? handled by a B-tree
- entry-to-inode? handled by a B-tree
- etc

But I know how to do it, how to write it, even if I used simply because I read a book about filesystems and XFS was described as the "original B-tree filesystem".

Now, for the arise-v2 softcore project, I have the need to "map" a ROM address into the corresponding line in assembly code that the "code flow" shows on the screen. There is a hardware debugger (project Otaku) inside the softcore; sort of telemetric thing that at the end of each "code-fetch" sends the CPU's context to the host (so I can verify that the HDL code is working as expected). Lines in the assembly source file are not synchronized to the lines of machine code, due to comments in the source file, due to included files, due to macros, and other stuff. Oh, and I also need to do vice versa: I need to map a machine address exported by the debugger into a line of one of the n files that compose a project, and for both these two purposes, I am thinking about recycling the same b-tree algorithm used for the toy filesystem.

That's why I got surprised to see an other binary-tree scheme.

[brucehoult]

But I know how to do it, how to write it, even if I used simply because I read a book about filesystems and XFS was described as the "original B-tree filesystem".

1993?

Apple's HFS, for example, was just a little earlier in 1985.

[Nominal Animal]

I also need to do vice versa: I need to map a machine address exported by the debugger into a line of one of the n files that compose a project, and for both these two purposes, I am thinking about recycling the same b-tree algorithm used for the toy filesystem.

Yup, you essentially have an ordered 1:1 map between machine addresses and source lines, and given one, need to match the other, with the twist that if the key is not listed, then use the nearest previous key instead.  There are many ways to implement it, but algorithmic reuse makes sense, as it makes the project easier to maintain, and a few percent speed difference between implementations is utterly insignificant in the grand scheme of things.

That's why I got surprised to see an other binary-tree scheme.

Oh, that binary search tree stuff is for LARGE datasets.  As in won't fit in RAM.  With sparse keys, too, say 2¹²⁸ or larger keyspace.  The reason to not use b-trees is when the dataset has a simple binary partitioning function, but no d-way partitioning function, nor any single-dimensional order.  For example, if your data are k-dimensional points, you can use a hyperplane to split the leftover set in two in any direction.  If the dataset is one-dimensional, then b-tree is more efficient (and you typically only need a small number of levels, maybe five to eight at most, even for huuuuge datasets, considering the currently-used page sizes, given typical key sizes).

(Rudolf Bayer and Edward M. McCreight invented B-trees back in 1971.)

[chickenHeadKnob]

But I know how to do it, how to write it, even if I used simply because I read a book about filesystems and XFS was described as the "original B-tree filesystem".

1993?

Apple's HFS, for example, was just a little earlier in 1985.

The B-tree concept dates back to late 60's, IBM mainframes had VSAM in the 70's, with VSAM being sort of b-tree with complications. nothing new under the sun you young whipper-snapper-shens

[brucehoult]

B-trees have been used for a long time within files, yes. However on most systems the disk blocks within a file were essentially a linked list. One of the big differences with HFS was that the list of disk blocks in every file on the disk were kept in one single B-tree for the disk, with {inode number, block number} as the key.

*not actually inode on a Mac, but similar

[legacy]

say 2¹²⁸ or larger keyspace

yup, the toy-filesystem has been implemented in the ROM of a Coldfire-v1 board that handles a parallel/ATA hard drive of 4Gbyte. It was too small for today Linux needs, so I was really tempted to throw it into the trash can it, but then I decided to reuse it for a hobby project. The hard drive is old but modern enough to let you set a data block of 1Kbyte of size, so 4Gbyte/1Kbyte is approximatively the order of magnitude of the maximal physical entries handled by b-tree.

With nodern hard drives (>= 1Tera byte) it's a very large keyspace 

[Nominal Animal]

Filesystems use B-trees (or variants) as opposed to binary search trees, because the data is essentially one-dimensional; the entries are naturally ordered, so there is no need or benefit in binary splitting.  B-trees just fit the use case much better.

HFS did have data and resource forks, but they were in different extents, referred to from the same catalog file b-tree entry.

Technically, we could have multidimensional files, or files composed of allocation block sized nodes in a directed graph or a tree... but since we can emulate those trivially using one-dimensional data (especially nicely on filesystems that support sparse files), it looks like one-dimensional data storage models suffice.  For us humans, at least.

[legacy]

What I found difficult regards the implementation. B-tree are usually implemented in a way they allocate leaves and nodes in ram, while in my case structures are entirely allocated on disk, so it's a b-tree that read a disk block of 1Kbyte and this contains leaves and nodes.

The original reason for this is that my Coldfire board had only 2Mbyte of ram, soldered on the motherboard and not expandable.

[hamster_nz]

Been reading & playing with the Hilbert Transform. It takes real-only samples and 'magically' makes them into complex samples. For example, if you feed in a cosine wave, the transform should (and does) gives you back the matching sine wave for the quadrature part.

Lots of interesting thoughts, like how the FIR filter has has the same coefficients as the spectrum of a square wave, because the frequency response needs to look like a square wave with negative frequencies get moved -90 degrees, positive frequencies move +90 degrees.

Code: [Select]

#include <math.h>
#include <stdio.h>

#define SAMPLES 1000
#define HALF_WIDTH 11  /* e.g. 11 filters from -11 to 11 */

float x[SAMPLES];

int main(int argc, char *argv[]) {
  int i;
  /* Build some test data */
  for(i = 0; i < SAMPLES; i++) {
     x[i] = cos(2*M_PI*i/10.3);
  }

  /* Now apply the Hilbert Transform and see what you get */
  /* It should be close to sin(2*M_PI*i/10.3) */
  for(i = HALF_WIDTH; i < SAMPLES-HALF_WIDTH-1; i++) {
    double h = 0;
    int j;

    /* Apply the kernel */
    for(j = 1; j <= HALF_WIDTH; j+=2)
      h += (x[i-j]-x[i+j]) * 2.0/(j*M_PI);

    /* Print result */
    printf("%8.5f, %8.5f\n", x[i], h);
  }
}


[Sam Hobbs]

I am not sure what the question is. Perhaps the Dictionary of Algorithms and Data Structures  is relevant.

[nigelwright7557]

One of my jobs is designing USB scopes.
I wrote most of the code myself.
However I wasn't an expert on FFT.
So I searched the WWW for an algorithm.
I downloaded about 3 that I plugged into my own C# code but none worked very well.
They seemed to be very noisy even with a nice sine wave from my sig gen.
It was a struggle but I eventually found one that worked well.

Code: [Select]

        /*
           This computes an in-place complex-to-complex FFT
           x and y are the real and imaginary arrays of 2^m points.
           dir =  1 gives forward transform
           dir = -1 gives reverse transform
        */
        int FFT(int dir, long m)
        {
            long n, i, i1, j, k, i2, l, l1, l2;
            double c1, c2, tx, ty, t1, t2, u1, u2, z;

            /* Calculate the number of points */
            n = 1;
            for (i = 0; i < m; i++)
                n *= 2;

            /* Do the bit reversal */
            i2 = n >> 1;
            j = 0;
            for (i = 0; i < n - 1; i++)
            {
                if (i < j)
                {
                    tx = x[i];
                    ty = y[i];
                    x[i] = x[j];
                    y[i] = y[j];
                    x[j] = tx;
                    y[j] = ty;
                }
                k = i2;
                while (k <= j)
                {
                    j -= k;
                    k >>= 1;
                }
                j += k;
            }

            /* Compute the FFT */
            c1 = -1.0;
            c2 = 0.0;
            l2 = 1;
            for (l = 0; l < m; l++)
            {
                l1 = l2;
                l2 <<= 1;
                u1 = 1.0;
                u2 = 0.0;
                for (j = 0; j < l1; j++)
                {
                    for (i = j; i < n; i += l2)
                    {
                        i1 = i + l1;
                        t1 = u1 * x[i1] - u2 * y[i1];
                        t2 = u1 * y[i1] + u2 * x[i1];
                        x[i1] = x[i] - t1;
                        y[i1] = y[i] - t2;
                        x[i] += t1;
                        y[i] += t2;
                    }
                    z = u1 * c1 - u2 * c2;
                    u2 = u1 * c2 + u2 * c1;
                    u1 = z;
                }
                c2 = Math.Sqrt((1.0 - c1) / 2.0);
                if (dir == 1)
                    c2 = -c2;
                c1 = Math.Sqrt((1.0 + c1) / 2.0);
            }

            /* Scaling for forward transform */
            if (dir == 1)
            {
                for (i = 0; i < n; i++)
                {
                    x[i] /= n;
                    y[i] /= n;
                }
            }

            return (1);
        }



[westfw]

I eventually found one

Where?  Written by whom?  What's the license?

[nigelwright7557]

I eventually found one

Where?  Written by whom?  What's the license?

Cant remember which site I got it off or who wrote it.

[brucehoult]

I eventually found one

Where?  Written by whom?  What's the license?

30 seconds with google finds:

http://paulbourke.net/miscellaneous/dft/

No license information on that page, but one level up http://paulbourke.net/miscellaneous says right at the bottom:

The contents of this web site are © Copyright Paul Bourke or a third party contributor where indicated. You may print or save an electronic copy of parts of this web site for your own personal use. Permission must be sought for any other use. Any source code found here may be freely used provided credits are given to the author. Purchase of credit free licenses of material found on this site can be negotiated with the author. The author can also quote for unique variations and/or higher resolution versions of the images found on this site.

[Nominal Animal]

Shows you the "care" typical proprietary developers have with copyrights... 

[nigelwright7557]

Shows you the "care" typical proprietary developers have with copyrights... 

Open source mate !
https://csharp.hotexamples.com/examples/-/FFT/-/php-fft-class-examples.html