spraci.info

Search

Items tagged with: math

Rook graphs and Paley graphs


An m by n rook graph is formed by associating a node with each
square of an m by n chess board and connecting two nodes with an
edge if a rook can legally move from one to the other. That is, two
nodes are connected if they are either in the same row or in the same
column.

A Paley graph of order q is a graph with q nodes where q is a
prime power and congruent to 1 mod 4. Label each node with an element of
the finite group F with q elements and connect two nodes with an
edge if the difference between their labels is a quadratic residue. That
is, for nodes labeled a and b, connect these nodes if there exist an
x in F such that ab = x².

We’ll look at a graph which is both a rook graph and a Paley graph: the
3 by 3 Paley... Show more...
 

Inverse trig function implementations


Programming languages differ in the names they use for inverse trig
functions, and in some cases differ in their return values for the same
inputs.

Choice of range


If sin(θ) = x, then θ is the inverse sine of x, right? Maybe.
Depends on how you define the inverse sine. If -1 ≤ x ≤ 1, then there
are infinitely many θ’s whose sine is x. So you have to make a choice.

The conventional choice is for inverse sine to return a value of θ in
the closed interval

[-π/2, π/2].

Inverse tangent uses the same choice. However, the end points aren’t
possible outputs, so inverse tangent typically returns a value in the
open interval

(-π/2, π/2).

For inverse cosine, the usual choice is to return values in the closed
interval

[0, π].

Naming conventions


Aside from how to de... Show more...
 

arctan( k tan(x) )


I recently had to work with the function

f(x; k) = arctan( k tan(x) )

The semicolon between x and k is meant to imply that we’re thinking
of x as the argument and k as a parameter.

This function is an example of the coming full
circle

theme I’ve written about several times. Here’s how a novice, a
journeyman, and an expert might approach studying our function.
  • Novice: arctan( k tan(x) ) = kx.
  • Journeyman: You can’t do that!
  • Expert: arctan( k tan(x) ) ≈ kx for small x.
Novices often move symbols around without thinking about their meaning,
and so someone might pull the k outside (... Show more...
 

The hardest logarithm to compute


Suppose you want to compute the natural logarithms of every floating
point number, correctly truncated to a floating point result. Here by
floating point number we mean an IEEE standard 64-bit float, what C
calls a double. Which logarithm is hardest to compute?

We’ll get to the hardest logarithm shortly, but we’ll first start with a
warm up problem. Suppose you needed to compute the first digit of a
number z. You know that z equals 2 + ε where ε is either 10^-100^ or
-10^-100^. If ε is positive, you should return 2. If ε is negative, you
should return 1. You know z to very high precision a priori, but to
return the first digit correctly, you need to compute z to 100 decimal
places.

In this post we’re truncating floating point numbers, i.e. rounding
down, but similar considerations apply when rounding to... Show more...
 

#Neutrinos Lead to Unexpected Discovery in Basic #Math | Quanta Magazine http://bit.ly/2CMYz1V

 

Just evaluating a polynomial: how hard could it be?


The previous
post

looked at an example of strange floating point behavior taking from book
End of Error. This post looks at another
example.

This example, by Siegfried Rump, asks us to evaluate

333.75 y^6^ + x^2^ (11 x^2^ y^2^ – y^6^ – 121 y^4^ – 2) +
5.5 y^8^ + x/(2y)

at x = 77617 and y = 33096.

Here we evaluate Rump’s example in single, double, and quadruple
precision.
#include <iostream>
&#35;include <quadmath.h>

using namespace std;

template <typename T> T f(T x, T y) {
T x2 = x\*x;
T y2 = y\*y;
T y4 = y2\*y2;
T y6 = y2\*y4;
T
... Show more...
 
Addition:

Image/photoivan zlax wrote the following post Tue, 12 Nov 2019 03:16:13 +0300

@ was born 30 years ago in USSR.
Image/photo
At NYU, he studied computer science at The Courant Institute of Mathematical Sciences, where he met the three friends with whom he founded DIASPORA\*, a social networking service, in 2010. The project
... Show more...
 
@ was born 30 years ago in USSR.
Image/photo
At NYU, he studied computer science at The Courant Institute of Mathematical Sciences, where he met the three friends with whom he founded DIASPORA\*, a social networking service, in 2010. The project was conceived after the founders had attended a lecture by Columbia Law School professor and free software activist Eben Moglen in February 2010 about the threat to privacy posed by commercial Internet services. According to Moglen, Zhitomirskiy was "immensely talented" and "the most idealistic of the group... He had a choice between graduate school and this project, and he chose to do the project because he wanted to do something with his time that would make freedom"
... Show more...
 
Proving a longstanding conjecture about the area of negatively curved spaces

https://m.phys.org/news/2019-11-longstanding-conjecture-area-negatively-spaces.html
"There are many possible shapes, and nature picks the one using the least amount of energy," Spruck says. It follows that the shape that encloses a given area with the smallest possible perimeter is the circle—or, venturing into three dimensions, the sphere.
....But things get trickier when you want to generalize this idea beyond circles and spheres to more complicated situations.

Back in 1926, the conjecture was proved for two dimensions. In 1984, it was proved for four dimensions, and for three in 1992. "Then we did all the other dimensions,"

The challenge, he explains, was that while the conjecture was relatively straightforward—if you're handy with math—in what's known as Euclidean space, things got more complicated in, say, negatively curved space.
Neg
... Show more...
 
Канадец живущий в Бразилии собирает на Kickstarter деньги на настольную игру по мотивам известной задачи о 7 мостах Кёнигсберга, решённой впервые Л.Эйлером.

Seven Bridges - A Stroll & Write Board Game


Come visit the historic European city of Königsberg and cross its famous seven bridges!
#russian #lang ru #Königsberg #math #boardgame #crowdfunding #history
 

Optimization, Dominoes, and Frankenstein


Robert Bosch has a new book coming out next
week titled OPT ART: From Mathematical Optimization to Visual Design.
This post will look at just one example from the book: creating images
of Frankenstein’s monster [1]using dominoes.


{.aligncenter
.size-medium width="623" height="913"}

The book includes two images, a low-resolution image made from 3 sets of
dominoes and a high resolution image made from 48 sets. These are double
nine dominoes rather than the more common double six dominoes because
the former allow a more symmetric arrangement of dots. There are 55
dominoes in a double nine set. (Explanation and generalization
here.)

... Show more...
 

More on attacking combination locks


A couple weeks ago I wrote about how De Bruijn
sequences

can be used to attack locks where there is no “enter” key, i.e. the lock
will open once the right symbols have been entered.

Here’s a variation on this theme: what about locks that let you press
more than one button at a time?

[1]Image/photo{.aligncenter
.size-medium width="400" height="467"}

You could just treat this as if it were a keypad with more buttons. For
example, suppose you can push either one or two buttons at a time on the
lock pictured above. Then you could treat this as a lock with 15
buttons: the five actual buttons and 10 virtual buttons corresponding to
the ten ways you could choose 2 buttons out of 5 to press... Show more...
 

Summing an array of floating point numbers


Adding up an array of numbers is simple: just loop over the array,
adding each element to an accumulator.

Usually that’s good enough, but sometimes you need more precision,
either because your application need a high-precision answer, or because
your problem is poorly conditioned and you need a moderate-precision
answer [1].

There are many algorithms for summing an array, which may be surprising
if you haven’t thought about this before. This post will look at Kahan’s
algorithm, one of the first non-obvious algorithms for summing a list of
floating point numbers.

We will sum a list of numbers a couple ways using C’s float type, a
32-bit integer. Some might object that this is artificial. Does anyone
use floats any more? Didn’t moving from float to double get rid of
all our precision problems? No and no.

In fact,... Show more...
 
#epo promoting illegal #swpats or #patents on #math under the guise of something called #websummit (yes, an insult to the WWW) https://twitter.com/EPOorg/status/1191443474148741122 http://techrights.org/wiki/index.php/Software_Patents_in_Europe
 

Any number can start a factorial


Any positive number can be found at the beginning of a factorial. That
is, for every positive positive integer n, there is an integer m
such that the leading digits of m! are the digits of n.

There’s a tradition in math to use the current year when you need an
arbitrary numbers; you’ll see this in competition problems and
recreational math articles. So let’s demonstrate the opening statement
with n = 2019. Then the smallest solution is m = 3177, i.e.

3177! = 2019…000

The factorial of 3177 is a number with 9749 digits, the first of which
are 2019, and the last 793 of which are zeros.

The solution m = 3177 was only the first. The next solution is 6878,
and there are infinitely more.

Not only does every number appear at the beginning of a factorial, it
appears at the beginning of infinitely many factorials.... Show more...
 

A simple unsolved problem


Are there infinitely many positive integers n such that tan(n) >
n?

David P. Bellamy and Felix Lazebnik [1]asked in 1998 whether there
were infinitely man solutions to |tan(n)| > n and tan(n) >
n/4. In both cases the answer is
yes. But at least
as recently as 2014 the problem at the top of the page was still open
[2].

It seems that tan(n) is not often greater than n. There are only
five instances for n less than one billion:

1\
260515\
37362253\
122925461\
534483448

In fact, there are no more solutions if you search up to over two
billion as the following C code shows.
#include <math.h>
&#35;include <stdio.h>
&#35;include <limits.h>

int main() {
... Show more...
 

Higher order Newton-like methods for root finding


There are variations on Newton’s root finding method that use higher
derivatives and converge faster. Alston Householder developed a sequence
of such methods of the form

Image/photo{.aligncenter
.size-medium width="243" height="78"}

where the superscripts in parentheses indicate derivatives. When n =
2, Householder’s method reduces to Newton’s method.

Once Newton’s method is close enough to a root, the error is squared at
each iteration. Said another way, the number of correct decimal places
roughly doubles. With the Householder method of order n, the number of
correct decimal places roughly increases by a factor of n.

The Householder method H~n~ can be written as a rational function of
f and... Show more...
 

Computing pi with bc


I wanted to stress test the bc calculator a little and so I calculated
π to 10,000 digits a couple different ways.

First I ran
time bc -l <<< "scale=10000;4\*a(1)"
which calculates π as 4 arctan(1). This took 2 minutes and 38 seconds.

I imagine bc is using some sort of power series to compute arctan, and
so smaller arguments should converge faster. So next I used a formula
due to John Machin (1680–1752).
time bc -l <<< "scale=10000;16*a(1/5) - 4*a(1/239)"
This took 52 seconds.

Both results were correct to 9,998 decimal places.

When you set the scale variable to n, bc doesn’t just carry
calculations out to n decimal places; it uses more and tries to
deliver n correct decimal places in the final result.

Why bc


This quirky little calculator is growing on me. For one thin... Show more...
 

Randomness


My attempt at defining randomness:

https://gitlab.com/drummyfish/my_writings/blob/master/randomness.md

e.g. the most random bytes I've found are:
00100101
00101001
01001001
01001010
01010010
01011011
01101011
01101101
10010010
10010100
10100100
10101101
10110101
10110110
11010110
11011010

#randomness #probability #math #python #fun
 

Generating De Bruijn cycles with primitive polynomials


Last
week

I wrote about a way to use De Bruijn cycles. Today I’ll write about a
way to generate De Bruijn cycles.

De Bruijn cycles


Start with an alphabet of k symbols. B(k, n) is the set of
cycles of that contain every sequence of n symbols, and is as short as
possible. Since there are k^n^ possible sequences of n symbols,
and every one corresponds to some starting position in the De Bruijn
cycle, an element of B(k, n) has to have at least k^n^
symbols. In fact, the elements of B(k, n) have exactly k^n^
symbols.

It’s not obvious that B(k, n) should be non-empty for all... Show more...
 
Later posts Earlier posts