Today, I released my NHD project known as ChemicalDevelopment presents “Kent State Shootings”.
I talk about the massacre itself, as well as the context surrounding the protests, such as the Vietnam war, Cambodian expansion, etc.
Here is our official ChemicalDevelopment anthem:
If you’d like to see the source, and make your own version, I used LMMS to create this. You can use my exact project, located here.
Flask boy approves of this message!
The chemicaldevelopment mailing list is group@chemicaldevelopment.us
.
To join the receive list, email group@chemicaldevelopment.us
with the subject [REQUEST] Join The Mailing List
, and a non-blank body of the message. You can add other mailing addresses you would like on the list in the body.
Make sure not to add spam/spam-like content, or it may be filtered!
Any questions can go there, about specific software, or just general ChemicalDevelopment chatter.
Here’s a link to posts about PGS
Essentially, PGS is a distributed computing program that I wrote to find polynomials which generate prime numbers.
I’ve made lots of updates to it, and plan on a released version in a few weeks.
Originally (and up to version 2.5.0), the bulk of PGS was written in JavaScript. I know, I know, it’s quite odd. I mainly used JS as an expirement, as it supports talking to firebase (the database we use) out of the box. It actually worked very well for cross-process communication and JSON-based datastructures well. Also, it was surprisingly easy to distribute (just include the ‘node’ binary and node_modules/ folder and it works!). However, the archives were 10MB, which was mostly the node binary. Also, there were limitations of using JavaScript and C together.
Python requires a custom library (called Pyrebase), which is unofficial and requires pycryptodome.
Still unclear, PGS only works in development mode now, and I will likely return to NodeJS, or use Python with better --offline
support, or possibly switch to C (although this is very unlikely).
Not yet, but that doesn’t mean we aren’t real.
It’s only as real as you make it
We’re always doing math, whether we realize it or not. Whenever you need to know how much tax is on something, or if you can evenly split pizza between people, you are using arithmetic.
Arithmetic is essentially all your number manipulations, adding, subtracting, multiplying and dividing. There are quite a few tricks we can use to speed up doing this in your head.
I’ll present the first part of this article in base 10, but later I’ll go into other bases as well.
Here is what is called grade school addition:
( 1 ) 248 + 543 _______ 791
the 1
on top is because 8+3=11
is greater than 10
, so we write the first digit lower, and the 10s place above the next.
The reason for this is quite simple: we can’t have a digit greater than or equal to the base. if we have a digit of (10) in one place, we know that is invalid, so we seperate it into 1
and 0
. The same applies here.
There aren’t really any improvements to this, because of how simple it is.
This is grade school subtraction:
(4 13 13) 5 4 3 - 2 4 8 ___________ 2 9 5
The numbers on top are because 3<8
, so we must “borrow” from the next place value.
Essentially, we are saying that because digits have to be between 0
and 9
, we will have a negative if we subtract 8 from 3, so we add on 10 knowing that 13 overflows, but that (13-8) will not.
The only real speedup here is that you could start by borrowing from the start, then carry digits later (so you won’t have to stop in the middle)
All in all, however, addition and subtraction do not have many speedups because of their linear nature.
This is grade school multiplication:
(12 ) 23 * 17 ______ 161 + 230 ______ 391
We take it digit-wise multiplication, 7*3, which is equal to 21. This is greater than 10, so we carry the 2
above to the next column.
Then, we compute 7*2=14
, and add the 2
which was our carry from last time, giving us 16
. our carry is now 1
Since there is no other digit, simply tack on our 1
and recieve the first product, 7*23=161
.
We move on to the next digit on the bottom number, 1
, and begin by adding a 0
under our 161
.
We move column to column just like last time to end up with 230
written. We then sum these two numbers to recieve 391
Pretty straight forward, but we can speed things up quickly.
Here are a few things to know:
Obviously, memorizing your multiplication tables for single digits speeds things up a lot for all of this.
say you have the number (ab)*(cd),
Where (ab) and (cd) are the digits in base 10
You can write these then as (10a+b)*(10c+d) (since each place value is multiplied by the base, 10)
When you expand this, you get 100*a*c+10*(a*d+b*c)+b*d
So, the digits are: (a*c)
, (a*d+b*c)
, and (b*d)
Applying this to our example, 23*17
, a=2, b=3, c=1, d=7
Our new number is (2*1)
, (14+3)
, and (3*7)
, or
(2)(17)(21)
Obviousy, we need to carry.
By adding the carry from each:
(2)(17)(21) (2)(17+2)(1)=(2)(19)(1) (2+1)(9)(1)=(3)(9)(1) 23*17=391
Once you get this down, multiplying two digit numbers can be faster, a quick example:
Compute 97*83
(9*8), (7*8+3*9), (7*3) (72)(56+27)(21) = (72)(83)(21) (72)(83+2)(1) = (72)(85)(1) (72+8)(5)(1) = (80)(5)(1) (8)(0)(5)(1) 97*83 = 8051
If you’ve ever read about primes, you have probably wondered how do we generate them? How do we find more?
If you haven’t read my post on primes, it is a good prerequisite to this post, so I’d suggest trying that first.
A form is a way to write something.
You can write $ 6 $ as $ 2n $ because $ 6 = 2 * 3 $. Here, $ n = 3 $, so it has this form.
$ 9 $ is part of a form: $ n^2 $ because $ 9 = 3^2 $. Here, $ n = 3 $
Forms of primes are formulas, like $ 2n $ or $ n^2 $ which hold primes.
For example, all primes except $2$ can be written as $2n+1$. If they were $2n$, then they would not be prime (except for $2$, of course)
Currently, world records for sizes of primes are being broken by GIMPS - which searches for Mersenne primes.
GIMPS searches numbers that are of the form: $ 2^n-1 $, and tests them for primality
Prime Grid searches lots of forms, most notably $ a2^n\pm1 $
They also search prime generators, which they broke a record for $an+b$ which is called AP26
What they found was for $ n = 0 . . . 25 $, $a * n + b$ is prime for $a = 23681770*223092870$ and $b = 43142746595714191$
Which broke the previous world record.
PGS is my program, which searches for polynomials which generate primes for the first values.
Currently, we are searching quadratics, which are of form: $an^2 + bn + c$. We haven’t broken any records yet, but we hope to soon. PGS is running on UTK’s (University of Tennessee Knoxville) super computer, Newton.
Although it is much faster than any home computer, users can donate their CPU time to check a small block of coefficients.
PGS is a project I have worked on for 3 months now, and just recently added user support and online record keeping.
Here’s how it works.
When you download a release, that includes a few things. A node
executable for your platform. Along with the programs:PGS.js
, lib.o
, CPGS.o
.
Note that PGS.js is just source, while the .o
files are compiled files. The source for everything in PGS is on Github
You enter in your email and password that you signed up with in my.prefs
, and click run.sh. It logs you in, then starts gathering workloads from my server, and runs each using CPGS.o
.
Once these finish, PGS grabs another one, and starts it. It keeps going and going until it is killed, or your prefs specify to stop. It then gracefully shuts down, and marks all of your jobs as incomplete, so the server knows you didn’t finish them.
You will notice a quite large file - primes.dat
which is 250MB. This is not downloaded in the zip. If PGS determines that you don’t have a primes.dat file, it generates one with lib.o
.
This is a bitset - which I’ll explain later - which stores information so I know whether or not every number below $2,000,000,000$ is prime. This is used later to verify whether numbers are prime.
I’ll go into specific parts down below.
I’m going to assume you know the binary number system for this part. If not, just think of 1 as a “yes” and 0 as a “no”.
So, there are plenty of algorithms to generate the first few primes. I use the Sieve of Eratosthenes to compute a list.
But, if we stored the primes as an array, like [2, 3, 5, 7] this would take up too much space. How much space exactly?
Well, 32 bit integers which can store up to 2^32 each take up 4 bytes because each byte is 8 bits, and 32 / 8 = 4
If we wanted to store each prime under 2,000,000,000, we would have to store over 98,000,000,000. This takes up more space, and is slower at runtime than a bitset, which is explained below.
This approach will take 98,000,000 integers of space (each is 32 bits, which is 4 bytes), and when we check at runtime, we will need to check every integer in the array until we find it, or we find a number that is greater than it.
For example, say I give you a small list of primes: [2, 3, 5, 7, 11, 13, 17, 19]. I ask you if 15 is prime. How do you tell me?
Well, you would go through the list and compare each to 15.
Is 2 = 15?
Is 3 = 15?
. . .
Is 17 = 15?
At this point, you can stop because you have passed where 15 would be, so you know it isn’t prime.
Now then, let’s say we use a list of bits to tell you if the number is prime. The list above would look like:
001101010001010001010
This starts at 0, and goes to 19
The 1
s mean that the index is prime, so count from the left: 0
, 1
, 2
001101010001010001010
The last number in red is 1
, which indicates that 2
is prime.
In this case, if I asked you to check if 15 is prime, you don’t need to go through all the numbers in the list; All you need to do is skip to 0 . . . 15, and check that single bit.
And for memory usage, the first approach uses 98000000 integers, whereas this one can store 32 numbers in a single integer (using the list of 1
s and 0
s), so we would need $2000000000/32 = 62500000$ integers.
So it uses about 60% as much memory as the first approach, and is much faster to use.
We store the array of integers from the second approach in a file, then read it back when you run.
So, it uses 250mb of ram per thread you run, which everyone should have.
This part is pretty straight forward. We run 3 for loops which check each possibiliy of a, b, and c within certain ranges.
Then, it keeps evaluating until it finds a value which is not prime. Once it does, if the number of primes was greater than 60, or it has at least 40 distinct in a row, it prints the result out.
It uses the file we created above to verify whether each number is prime, by checking the $(an^2+bn+c)$th bit of the list of 1
s and 0
s
So, say we are testing $f(n) = an^2+bn+c$
We first plug in n = 0, and we test whether $a0^2+b0^2+c$ is prime
Then, n = 1, and so on until the function isnt prime.
We were given info collected about PE (Physical Education) students at L&N, including mile run times, number of push ups in a minute, and curl ups in 2 minutes.
You can find all of our info here
You can go to File>Make A Copy to view and edit
Although some classes had very few responses, $ L $ day and $ N $ day both made up around $ 50\% $ of the total responses, which is what you would expect.
Some classes did not have all members ($ N4 $ only had 1 response), a good number of people from all made up a large database that accurately respresents mosts of the population.
Most of the responses were from males, though it wasn’t too horribly biased. There were still $ > 40\% $ females, so it is still quite reliable.
Some explanations might be: females choose not to take PE as much as boys do, or that boys responded at a higher rate than females.
All values are in minutes. So, 2.5 is 2m30s
Mean (Average) | Median (Middle Value) | Standard Deviation (How dense is the set?) |
12.3 | 12.1 | 3.4 |
What this tells us is that on average, you will run around a $ 12.25 $ minute mile, and that $ 68\% $ of students run a mile between $ 8.88 $ minute and $ 15.62 $ minutes (which is generated by $ mean \pm deviation $)
Lots of students finished in the $ (-\infty, 15] $ range we can see there are significantly more than in the corresponding range, $ [15, \infty] $ respectively.
This makes sense due to the way students flock together when running or jogging.
These values are in pushups per 1 minute
Mean (Average) | Median (Middle Value) | Standard Deviation (How dense is the set?) |
12.2 | 12 | 8.1 |
The standard deviation is very large, which means the amounts vary from the mean, which is evident by the few on the far left of the spectrum. Again we seem to see groups emerge, and this means that certain people are staying almost exactly in sync with each other.
We can say that about $ 68\% $ of students do between $ 4 $ and $ 20 $ pushups in one minute. This is a very large margin due to the size of the standard deviation.
These values are in curlups per 2 minutes
Mean (Average) | Median (Middle Value) | Standard Deviation (How dense is the set?) |
34.4 | 30 | 17.3 |
The standard deviation is even larger for this dataset, which means the amounts vary more from the mean. This is surely the case, if you look at the right side, there is a group of just over 30 students who did between 60 and 65 Curlups in 2 minutes. These few threw off the average and standard deviation quite a bit from what it would have been, and based on the evidence, it would seem that people, in general, find curlups much easier than pushups, and a small group finds them extremely easier than pushups.
A sum is addition of a sequence of numbers.
The sum of $1, 2, 3, 4$ is $1+2+3+4$, which is $10$
Essentially, infinite sums are the limit when you add an infinitely long sequence of numbers.
For example, if we add $ 1/n $ for n = $1, 2, 3, 4 . . . \infty$, the limit does not exist; it keeps getting larger and larger.
But, if we add $ 1 / (n^2) $ for n = $1, 2, 3, 4 . . .\infty$, the limit does exist. It is roughly $1.645$ (we’ll look at this one a bit lower)
Here are some more famous examples of infinite sums (they are values of the riemann zeta function)
Or
Or even
The first two are examples of infinite sums, and the third is an infinite product. Sum means adding, product means multiply. In all of these examples, we take them out to infinity (theoretically), and this is the answer we would get. In fact, as we go farther, they get very close to these values.
Before I show you these examples, we are going to look at sums a little bit more generally.
I’ve written a JSFiddle so you can enter your own series and watch the value it converges to.
Full version at https://jsfiddle.net/CadeBrown/tdxofngq/
You can just type in “n”, and it will show you the sum of 1 + 2 + 3 + 4 + … + n (which happens to be $ \frac{n(n+1)}{2} $)
A few cool sums to try in it: (copy the shaded part into the “series definition” box)
pow(-1, n) / n
pow(-1, n) / (2 * n + 1)
pow(n+1, -2)
Those 3 series above are what are called convergent series. Convergent means that if you keep evaluating more and more terms, it tends towards a limit.
Like $ \ln{2} $, or $ \frac{\pi}{4} $ were the limits of the first and second sum.
The first 3 sums converge quite slowly, and to get $d$ digits of precision to the “actual value” (if we could take it to infinity), we would need roughly $10^d$ terms. So, to get one more digit of precision, we would need 10 times as many terms to sum! That is why the first 3 are not good ways to calculate their sum ($\pi$, $\ln{2}$, etc)
There exists formulas for $\pi$ that require only $\frac{d}{14}$ terms to get $d$ digits, such as this one:
12 * (pow(-1, n) * fac(6 * n) * (13591409 + 545140134 * n)) / (fac(3 * n) * pow(fac(n), 3) * pow(640320, 3 * n + 1.5))
With this, we have $\frac{1}{\pi}$ in an efficient series
In fact, that series (with a few optimizations) is how record number of digits of $\pi$ are computed: Numberworld.
First post on this blog, so I thought we would start it out with something interesting, like primes.
We include some JSFiddles so you can see all the code available with it!
So, lets start out with what they are.
Most of the time, you might get something like
A prime is any positive integer greater than one whose only postive divisors are 1 and itself
but I prefer to say that a prime is any integer that you can’t make by multiplying two other integers.
For example, 2 is the first prime, 3 is the next. 4 isn’t a prime, though, because 4 = 2 * 2, which means it has other divisors (2), and thus can be made my multiplying two other integers.
I’ve written a little JSFiddle so that you can see if a number is prime. This is a very unoptimized version of primality testing (testing if a number is prime), but you can see how a basic version works.
Full version at https://jsfiddle.net/CadeBrown/x9h5buwa/
This program takes the remainder dividing your input by all numbers less than it (actually, the square root of it, but that is a simple optimization), and if it is zero, that means the number is divisible by some other number, and is therefore not prime.
One common question is
Why isn’t 1 or 0 prime?
And this was a large argument for years. 1 and 0 are not considered prime for a few reasons. The first is the nice property that is called unique factorization, which states that any given integer has exactly one way to factor into primes. For example, 12 = 2 * 2 * 3, and you can’t get 12 from any other primes than 2, 2, and 3. If we said that 1 is a prime, we could have 12 = 2 * 2 * 3 and 12 = 2 * 2 * 3 * 1 . We have agreed that this is a nice property to have. 1 is what is called a unit. As is negative one, which brings us to our next question:
If 2 is a prime, then isn’t -2 ?
And the answer is: Sort of.
This is because -2 is similar to +2, one is multiplied by the unit 1, while the other is multiplied by the unit -1 . We only consider a number prime if it is positive, though.
Are there infinitely many primes?
Yes, there are. Primes get very far apart (however, there are infinitely many primes exactly 246 apart (https://www.quantamagazine.org/20141210-prime-gap-grows-after-decades-long-lull/))
I’ve written a little fiddle to graph how quickly the number of primes grows, and a few approximations to the actual line
Full version at https://jsfiddle.net/CadeBrown/cfg8bgLt/
Primes have been in people’s thoughts ever since hunter-gatherer days (They thought about dividing food up. How do you give out 13 orange to 3 people?).
Primes are something that are so tangible, like rearranging fruits to divvy up, but yet so mysterious, we don’t even know if there are infinitely many primes that differ by 2!
People have studied primes initially for dividing up resources, which is still useful today, but primes are also used in cutting edge technologies, such as cryptography. While I won’t get into cryptography in this post, suffice it to say that bigger primes are more secure to encrypt data and then decrypt it because the hacker in between doesn’t have the computing power to factor out large primes (which is a very computation-heavy task).
Currently, the largest known prime is $ 2^{74,207,281}-1 $ which is more than 22 million digits long!
The largest prime found by hand was $ 2^{127} - 1 $, or $ 170,141,183,460,469,231,731,687,303,715,884,105,727 $ Imagine doing that by hand!
Just think about that for a second. No two integers can be multiplied to get $ 2^{127} - 1 $, but $ 2^{127} $ is just 2 multiplied by itself 126 times!
Another reason I like that number is the fact that $ 2^{127} - 1 = 2^{2^{7} - 1} - 1 = 2^{2^{2^{3} - 1} - 1} - 1 = 2^{2^{2^{2^{2} - 1} - 1} - 1} - 1 $
Subscribe to this blog via RSS.
Math 4
Software 3
School 1
Pgs 2
Question 1
Music 1
Politics 1
Vietnam 1
Notes 1
Math (4) Software (3) School (1) Pgs (2) Question (1) Music (1) Politics (1) Vietnam (1) Notes (1)