DEV Community: ian-a-frankel

The Fast Fourier Transform

ian-a-frankel — Thu, 21 Dec 2023 05:35:31 +0000

Introduction

Fourier analysis has many applications in signal processing; in this note we will discuss an algorithm that helps us more quickly determine understand a signal. Our motivating example comes from music theory, and breaking a sound wave into components.

Let f be a continuous 1-periodic function on $R\mathbb{R}$ , i.e. assume f(x) = f(x+1) for all x. We know a family of continuous functions f with this property, namely

$sin⁡(2πnx),cos⁡(2πnx)\sin(2\pi n x), \cos(2\pi n x)$

and it turns out that these are the building block for all 1-periodic functions. The idea is that we can decompose f as

\sum_{n = -\infty}^{\infty} a_n e^{2\pi i n x}

where for all real t,

e^{i t} = \cos(t) + i \sin(t).

We won't discuss issues of convergence here, but the idea is that any function of the form a sin(mt) + b cos(mt) is just a simple wave with period $2π/m.2\pi/m.$ and if we are willing to use a large enough N, then

∑n=−NNane2πinx\sum_{n = -N}^{N} a_n e^{2\pi i n x}

should be a very good approximation for f(x).

However, we could be dealing with a whole range of frequencies, not just integer frequencies, and in this case our combination of simple sound waves is more "smeared out", but f(x) is still a combination of the simple periodic functions $e2πixξe^{2\pi i x \xi}$ for $ξ∈R:\xi \in \mathbb{R}:$

f(x)=∫−∞∞f^(ξ)e2πixξ dξ f(x) = \int_{-\infty}^\infty \hat{f}(\xi)e^{2\pi i x \xi} \, d\xi

where $f^\hat{f}$ is the Fourier transform of f.)

In the case of a discrete spectrum of frequencies, the coefficients be computed as

a_n = \int_0^1 f(x)e^{-2 \pi i n x } \, dx.

In the case of a continuous spectrum, we have

f^(ξ)=∫−∞∞f(x)e−2πixξ dx. \hat{f}(\xi) = \int_{-\infty}^\infty f(x)e^{-2 \pi i x \xi} \, dx.

There are many physical applications of this, but we'll stick to one example. Assuming a measured sound wave is approximately a periodic function we can decompose it into simple waves with period n (frequency 1/n) and amplitude

a_n|^2 + |a_{-n}|^2)^{1/2}.

where n varies over the non-negative integers. The value of |a_n| which are largest tell us the frequencies that dominate the auditory signal.

Perhaps the most familiar idealized example of this is breaking a musical chord into individual notes, each of which has its own frequency.

Discrete Fourier Transform

In computer science we want to find a discrete approximation, and we do this by sampling a finite number of values of a function and approximating sums with integrals.

If we want to assume we are sampling over a long period of time and also sampling frequently, we can the frequencies we care about are from -M to M and we sample every value of x that is a multiple of 1/M and get a good enough approximation of our data on the whole real line.

(This gives us 2M^2 + 1 data points).

However, due to the nature of the exponential function, our analysis is going to be exactly the same for any collection of equally spaced points, and we can play around with the number of data points a little bit to make it more convenient.

For simplicity we'll say the value of f is sampled at N equally spaced points, and define the discrete Fourier transform as follows:

f^(k)=ak=∑n=0N−1f(n)e−2πink.\hat{f}(k) = a_k = \sum\limits_{n = 0}^{N-1} f(n)e^{-2\pi i n k}.

Then we can in fact say that for each of the values of n from 0 through N - 1,

\frac{1}{N} \sum\limits_{k = 0}^{N-1} a_ke^{2\pi i n k}.

Again, recall that f is the data that is detected by our microphone and the values of a_n are what we actually care about to determine the actual signal.

Now on the surface, it would appear that computing the whole list of values

a_k = [a_0,a_1,...,a_{N-1}]

requires $O(N^2)$ arithmetic operations in addition to calculating N values of the (complex) exponential function - after all, for each of N Fourier coefficients a_n we compute N products.

The Fast Fourier Transform

We can greatly reduce the number of computations needed by thinking of the Fourier transform as a whole instead of as a N individual values to compute, and in fact reduce to O(N log N) arithmetic operations for suitable N. We will describe this in the case where N is a power of 2. This method is known as the radix-2 Cooley-Tukey algorithm.

Let's define our FFT to be a function that takes as input an integer N = 2^m and a list L of values of length N. Here's python-like pseudo-code that computes the FFT much faster. (There are packages that handle complex numbers in python so this is actually pretty close to what we would write.)


def FFT(L, N):
    if N == 1:
        return L[0]
    evens = L[::2]
    odds = L[1::2]
    A = FFT(evens, N // 2)
    B = FFT(odds, N // 2)
    u = e^(-2pi i/N)
    U = [1]
    for n in range(N // 2):
        if n > 0:    
            U.append(U[-1]*u)
    C = [A[n] + U[n] * B[n] for n in range(N//2)]
    D = [A[n] - U[n] * B[n] for n in range(N//2)]
    return C + D

We remark that A + B is list concatenation, not vector addition. For the purposes of a human doing the verification, U[n] is just u^n, but we want have to compute all of these powers in O(n) time.

It really only takes a couple of lines of algebra to verify that the recursive formula for the Fourier transform is correct at each position: That is, we take the Fourier transforms for our function sampled at even-numbered positions only and at odd-numbered positions only, and simply check that for each k, our recursive formula has the correct coefficient of L[k]. Then we add them together, making one phase shift for the odd-numbered values to get the front half of the full sequence of coefficients, do the same with a different phase shift for the back half.

We can see there is a serious speedup. If an algorithm required quadratic time, two times through the algorithm on data of size N would still take $Θ(N2)\Theta(N^2)$ additional steps to reach the amount of time needed to perform the algorithm on data of size N. But we can clearly see that only O(N) additional steps are needed to make this leap, so the FFT is definitely much faster than computation directly from the definition.

Primality Testing

ian-a-frankel — Wed, 29 Nov 2023 22:48:22 +0000

Number Theory Basics

Most algorithms in cryptography depend on large prime numbers, and the fact that certain algorithms are hard. Encryption is basically the act of applying a mathematical function for which it is very hard to determine the inverse function without a key, but easy with the key.

There are many number theoretic algorithms which are fast and easy. The mother of them all number theoretic algorithms is Euclid's algorithm for finding the greatest common divisor:

Given that we can do division with remainder, if $a > b$ and we want to compute GCD(a,b) we write

$a = b q + r,$ and notice $GC D (a, b) = GC D (b, r) .$ Now we can iterate this. This is very fast; in fact its time complexity is $O (l o g (a + b))$ !

If $a$ and $b$ are really large and hard to factor, we can compute their GCD extremely quickly without knowing how to factor them! In fact there is no known way to efficiently determine the prime factorization of a number - if I multiply two random 300-digit primes $p$ and $q$ it's impractical to find $p$ and $q$ if you only know the value of $pq,$ although it is pretty easy to detect that $pq$ is not prime. You could write code to do it, but your computer would not last long enough to execute it.

Powers modulo $p$

If $d$ is an integer, we write $\equiv b ~ (mod ~ d)$ if $a$ and $b$ have the same remainder when we divide both by $p .$

If $p$ is a prime number, we can define multiplication on

{0,1,...,p-1}

by taking the result mod p, that is, taking the remainder when we divide by

p .

We can also define exponents in a similar way:

a^n

is just the remainder when

a^n

is divided by

p .

How do we actually compute $a^n$ efficiently when $a, p, n$ are all large?

The answer is repeated squaring. We can write $n$ as a sum of powers of $2$ , and calculate those powers of , i.e. if $n = 453,$

453 = 256 + 128 + 64 + 4 + 1 = 2^8 + 2^7 + 2^6 + 2^2 + 2^0.

So if we want to compute $17^{453},$ we actually only have to calculate the powers of $17$ whose exponents belong to

[1, 2, 4, 8, 16, 32, 64, 128, 256] .

All told, this is only

12

multiplication operations to compute

17^{453}

(

8

to compute the powers with exponents in the list, and

4

more to get the correct one).

Logarithms modulo $p$

Another well known fact in number theory: for any prime number $p,$ you can find a remainder $a$ such that all of the different powers $a, a^2, a^3, a^4, ... , a^{p-1}$ are different mod $p$ ; in this case we say that $a$ is a primitive root mod $p .$

We can get at most $p - 1$ different remainders, since no power of $a$ will give a remainder $0$ . Most values of $a$ will not be primitive roots, but in practice it usually not that hard to find one such value fairly quickly.) Values of $a$ with this property are called primitive roots. For example, the primitive roots mod $5$ are $2$ and $3$ .

powers of 1: 1,1,1,1 (not all distinct mod 5)
powers of 2: 2,4,8,16 (all distinct mod 5)
powers of 3: 3,9,27,81 (all distinct mod 5)
powers of 4: 4,16,64,256 (not all distinct mod 5)

For a = 1,2,3,4 we have

$5)a^4 \equiv 1 ~ (mod ~ 5)$

In fact, if $p$ is a large odd number and $1 < a < p - 1$ and
$p)a^{p-1} \equiv 1 ~ (mod ~ p)$ then $p$ is almost certainly prime, although there are a small number of "pseudoprimes" that pass this test which are not prime.

However, we can detect these pseudoprimes quickly with high probability! And we will want to do this, because even a failure rate of 1 in a million is enough to cause a lot of problems for a company like Google or American Express.

The Miller-Rabin Primality Test

However, if $p$ is a large pseudoprime that managed to sneak past the Fermat test, there are two cases that we might have to worry about here. The first is that the pseudoprime p could be a power of a prime, say p = $p = v^k$ where $v$ is prime.

Then $p$ is already extremely unlikely to escape the Fermat test - a random guess will only pass with probability 1 in $v^{k-1}.$ A relatively small number of Fermat tests with randomly chosen values of $a$ will detect that $p$ is not prime with an acceptably low failure rate.

For any true prime $p$ and primitive root $a$ we know $p)a^{k(p-1)/2} \equiv p - 1 ~ (mod ~ p)$ if $k$ is odd, and 1 if $k$ is even, and 1 and $p - 1$ are the only two square roots it has.

The other case is when $p = v w$ where $v, w$ are odd and greater than 1 but and have no prime factors. We can take advantage of their existence without being able to find $v$ and $w .$

Anything that is 1 (mod $v$ ) and $w - 1$ (mod $w$ ) will be another square root in of 1 in mod $p$ arithmetic, which will be different from 1 and $p - 1.$

Now, the key idea here is that if I pick a random integer from 0 to $p - 1,$ the remainders mod v and mod w are independent and uniformly distributed. What we do here is decorate the Fermat test a little bit.

First, find the unique odd number d for which we can write

\cdot 2^e.

Now, we will do Fermat tests, with a random number $a$ as before, but keep track of sightly more information. In what follows, all calculations are to be reduced modulo $p .$

1.) Let $m = a^d.$

2.) Calculate $m, m^2, ... , m^{2^e}.$

If the last result isn't 1, you have failed the Fermat test and you know the result is composite. However, even if you did not, you can look at the last power of m in the list for which the value was different from 1. If it's not $p - 1,$ then you have failed the Rabin-Miller primality test.

There's an entirely elementary proof that the Rabin-Miller test fails with probability at least 1/2 when $p$ is not prime.

Sharing Secrets using Primes

We can think about logarithms as the inverse of exponentiation, similarly to how we do for positive real numbers. log( $b$ ) ( with base $a$ ) is the power $n$ for which $a^n$ = $b .$

The key fact here is that when $p$ is a large prime number, the "logarithm" operation is computationally intractable.

Given $a$ and $n,$ it's easy to find $a^n.$ However, if we know the values of $a$ and $b,$ in general it is quite hard to find $n$ such that

a^n ~ \equiv ~ b ~ (mod ~ p).

So here's a quick way for two parties to exploit this fact and pass information while maintaining their own privacy:

Alice and Bob have a shared prime number $p, q$ and primitive root $a .$ (In fact $a$ doesn't need to be a primitive root, but needs to just have many distinct powers.)

Each has a private key, say $x$ for Alice and $y$ for Bob (they named them after their sex chromosomes).

Alice tells Bob $a^x$ and Bob tells Alice $a^y.$

The values of $x$ and $y$ are secure (difficult for either to steal from the other or for an eavesdropper to intercept), but they can both access the value of $a^{xy}$ to decrypt any information that needs to be available to both of them.

In fact the standard cryptographic system is a small variation on this: Instead of a large prime, we choose a product $q$ of two large primes in place of $p$ and a number like $a$ in place of $p$ , and those two pieces of infomration combined are Alice's public key. This has the additional layer of security that the exponent we must raise a number to to get 1 (mod $q$ ) is hard to compute.

Passing Information in React

ian-a-frankel — Tue, 07 Nov 2023 06:41:04 +0000

Introduction

In this post I will discuss what I recently learned about the JavaScript React library. While working on previous projects, I had few experiences understanding how different javascript files interacted with each other.

By chance I learned that two scripts simultaneously operating on the same DOM can be aware of each other's variables if they are both imported directly into the html file, so some information is passed through the DOM. However, in an ideal world, a developer should want to understand and control exactly what information each file is aware of.

Prelude: States

One of the key features of React is that instead of directly manipulating the DOM and using JavaScript event listeners, it instead causes the page, or components of the page, to re-render when the states of relevant variables are changed.

For this we import the useState hook from react, which allows us to create variables whose values can only be changed by calling the corresponding setter functions. Many things can be controlled by a single state.

React Components

The main building blocks of a project in React are called components. A common convention is to put each component is in its own .js file, and pairs of files communicate via import and export commands. I'm not sure if this is strictly necessary, but in all applications I am aware of we arrange components in a hierarchy whereby the parent imports functions that are exported by the child.

A react component is formatted with almost everything except the import and export commands inside the body of a function. When we set the function to return a value expressed in JSX format, it returns html elements for rendering. We won't discuss all of the details of the syntax here, but if we have a function called Header with properly specified JSX return values, it may be called as by a parent, and DOM elements may be created according to the value returned by the Header function.

Here is some sample from a React component, which I modified as an exercise:

(Source for all code in this post: https://github.com/ian-a-frankel/react-hooks-information-flow-lab)


//App.js

import React, { useState } from "react";
import ShoppingList from "./ShoppingList";
import itemData from "../data/items";
import Header from "./Header.js"

function App() {

  const [isDarkMode, setIsDarkMode] = useState(false);

    function onDarkModeClick() {
      setIsDarkMode((isDarkMode) => !isDarkMode)
    }

  return (
    <div className={"App " + (isDarkMode ? "dark" : "light")}>
      <Header isDarkMode={isDarkMode} onDarkModeClick={onDarkModeClick}/>
      <ShoppingList items={itemData} />
    </div>
  );
}

export default App;

We will discuss the meaning of all parts of the code, first starting with import and export.

Import and Export

The export command at the end tells us that the App function, which is in some sense the body of the file, can be imported and called in another file. The import commands tell us what information is being imported from other files; the relative paths of imported files must be specified. In particular, we see 'Header.js' and 'ShoppingList.js' are in the same directory as 'App.js', while 'items' is in the data directory which shares a parent directory with 'App.js'. Header and ShoppingList are functions that App calls.

Passing Props

The functions Header and ShoppingList do not have access to the variables in App by default. Instead, we specify which information the children functions can access by passing them as props.

Functions in JavaScript are a type of object, and we are simply specifying some of their key-value pairs.

In order for the ShoppingList function to access this information, we need to specify it as an argument, which we do here:


//ShoppingList.js

function ShoppingList({ items }) {

For reasons beyond the scope of this post, props are wrapped in braces and passed as objects, and then destructured back into variables in their initial form. The value for the key 'items' was specified in App.js when ShoppingList was called.

We note that the function ShoppingList must be exported in order for it to be imported into App.js.

States and Rendering

So far we have seen how a function that is called can be fed information from a parent, but how does it actually influence the values of variables in the parent? The answer is that we call the functions that have been passed as props. Let's take a look at some of the code from the Header component, whose output contains a button element that toggles Dark Mode and Light mode when clicked. The text of the button is conditional on whether the state of the 'IsDarkMode' is true or false:


function Header({isDarkMode, onDarkModeClick}) {

    return (
        <header>
        <h2>Shopster</h2>
        <button onClick={onDarkModeClick}>
          {isDarkMode ? "Dark" : "Light"} Mode
        </button>
      </header>
    )
}

export default Header

However, we can see that this is not the only thing that is changed when the state of 'IsDarkMode' changes. The return value of App contained the following element:

<div className={"App " + (isDarkMode ? "dark" : "light")}>

The state variable does not just affect the elements that it is passed to as a prop. This div element is rendered with CSS styling, and the styling depends on the class of the html element. Because the function 'onDarkModeClick' that was passed as a prop has scope up to the App component, interacting with its child the Header component can affect elements in App which are outside of Header. In this way we see information is communicated back up the component hierarchy.

Disadvantage: Burden of Passing Props

In a large program, there can be many layers of nesting between components and it is a lot to remember which props are passed where. We can bundle together props in a 'context' object with React's createContext hook, and then access them in a descendant with the useContext hook, potentially skipping many intermediate components. However, all React components in the DOM that use a context must be children of a context-providing "provider" DOM element. These additional steps typically only justify themselves when a prop has to be passed many times, so we do not include an example here.

The Document Object Model

ian-a-frankel — Wed, 18 Oct 2023 17:08:07 +0000

The first thing that struck me about javascript, in contrast to other programming languages I had seen before, was the way that variable assignments worked. All of this made more sense in the context of the document object model or DOM, which was my first real experience with different files interacting dynamically.

Javascript DOM manipulation makes the browser to render modifications to the page from the original html, without saving over the underlying html files.

Two Distinguishing Features of Javascript

The first difference with other programming languages was that you can declare constant variables. This sounds like an oxymoron, and on first reading I understood this to mean that they could never be modified in any way, which isn’t exactly true. Most of these variables are objects. A javascript object is a collection of key-value pairs. You are in fact allowed to modify the values for keys for an object variable declared as constant, so you can in fact meaningfully modify constant objects, but there are constraints.

The second thing that struck me was that when you assign a new variable Y to a preexisting object X, you can change the original object using code that only referred to the copy. By default we are just creating a pointer to an existing variable in memory, which was quite different from all other programming languages I had seen.

This seemed to me like a disastrous way to design a programming language, though it turns out that there are other methods, such as the spread operator, which allow us to copy objects and modify only the copy. Pointing to an existing object really did not seem like the intuitive default choice until I better understood how most javascript works.

Justifying these Features

All of this started to make more sense in the context of the Document Object Model (DOM). Elements in the DOM are nested as a tree structure within the body of the page. For example, within the body (the root of the tree), you can have tables or lists or drop-down menus or various kinds of content, and within these, some elements could have more things nested inside them.

When one of these elements is a script it can manipulate the other elements; here is an example of how this manipulation works.

STEP 1:

Declare an object variable (usually a constant variable) whose value is an html element. Often this element will already exist within the html document. There are query functions in javascript that allow us to efficiently select objects from the html.

Example code:

const frogImage = document.getElementbyId('frog-image')

The variable frogImage now points to a preexisting html element; in the html file, if the html file contains an element with the id 'frog-image'.

It is also possible to declare a variable that points to an object that does not exist within the DOM by just specifying that it is a certain type of html element. This element may be inserted into the DOM later, at which point it will be rendered in the browser.

Example:

const frogImage = document.createElement('img')

This creates an abstract image element which does not exist anywhere on the page. But we can select some kind of container in the DOM, for example, a formatted collection of animal pictures, and insert our abstract image element into that container, causing it to render inside that container on the page:

Const animalsDiv = document.getElementById('animal-pictures');

animalsDiv.append(frogImage)

STEP 2:

Write code that describes the ways in which you want to specify the object’s properties. If the object actually points to that object and inherits its attributes, like its location on the page, or its formatting, text content, or whether it even renders in the page at all.

Example:

Now that the javascript object frogImage points to an object, we can change the picture it shows it by changing its source attribute:

frogImage.src = 'https://encrypted-tbn0.gstatic.com/images?q=tbn:ANd9GcRjqJVxmFA_0Qr6AEo6ZomYD4jPnQQ8aRT6E_cnwQim_CGh3dW_3jh1b6FFvdsvH2bKy2g&usqp=CAU'

On the browser page, this will place the picture with the source (in this case URL) in the place of the element that is identified as frogImage in the javascript when the code is executed.

STEP 3: Create the conditions under which the code in step 2 is executed, based on the user's interactions with the page.

This is done by creating event listeners, which allow the browser to respond to the user's action. Events can include things like clicks, mouseovers, or pressing keys. For example, if we wanted to create a pop-up alert that said "ribbit" when the frog was clicked on, we could use the following command:

frogImage.addEventListener('click', alert('ribbit'))

I feel these are the key concepts underpinning dynamic rendering of webpages. Other topics, like communication with other pages and servers vastly expand site capabilities. We may explore these properties in future posts.

DEV Community: ian-a-frankel

The Fast Fourier Transform

Introduction

Discrete Fourier Transform

The Fast Fourier Transform

Primality Testing

Number Theory Basics

Powers modulo ppp

Logarithms modulo ppp

The Miller-Rabin Primality Test

Sharing Secrets using Primes

Passing Information in React

Introduction

Prelude: States

React Components

Import and Export

Passing Props

States and Rendering

Disadvantage: Burden of Passing Props

The Document Object Model

Powers modulo $p$

Logarithms modulo $p$