The Universal Language of Math
FRACTRAN is an esoteric programming language invented by John Conway (Game of Life). It is know to be Turing complete; this means that for any program you can write in, say, Java you can write a program in FRACTRAN to compute the same function. Since FRACTRAN programs "compute" sequences of integers, this would involve some encoding schemes (as in the example to follow).
A FRACTRAN program is an ordered list of positive fractions together with an initial positive integer input n.
The program is run by updating the integer n as follows:
1) for the first fraction f in the list for which nf is an integer,
replace n by nf
2) repeat this rule until no fraction in the list produces an
integer when multiplied by n, then halt.
Here is one program in FRACTRAN:
(Conway's video at Berkley actually uses this sequence) 17 78 19 23 29 77 95 77 1 11 13 15 15 55 --, --, --, --, --, --, --, --, --, --, --, --, --, -- 91 85 51 38 33 29 23 19 17 13 11 16 2 1and here, we start with integer n=2.
Execution:
-- We start with some n (here, =2), and generate a sequence of integers. -- The next value of n will be the result we get by multiplying current n by the first fraction in the FRACTRAN program (the sequence, left to right) that gives us an integer result. -- We terminate when no fraction in the sequence gives us an integer when multiplied by current n.
Executing it, this FRACTRAN program generates the following sequence of integers:
2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, ...
After starting with n=2, this sequence occasionally contains numbers
which have powers of 2 when prime factored,
and here are the powers of 2 that show up (in the order they occur):
2^2 = 4, 2^3 = 8, 2^5 = 32, 2^7 = 128, 2^11 = 2048, 2^13 = 8192, 2^17 = 131072, 2^19 = 524288, …The exponent part of these powers of two are the primes (in order): 2, 3, 5, 7, 11, 13, 17, etc.
John Horton Conway passed away in April 2020 (aged 82) from Covid-19.
Apply here (bit.ly/PH24APPLY) to be a Pearl Hacks Director! DEADLINE: Wednesday, Apr. 5th, 2023 11:59 PM EST ** NO computer science experience required. People of all genders and majors are welcome to apply, but you must be a UNC student! Pearl Hacks is a beginner-friendly hackathon at UNC for women and gender non-conforming students. Get involved with the technology field and leadership experience by applying to join our Board! This is also a great way to get involved with UNC computer science! Pearl Hacks is where you can help under-represented people, specifically women and gender non-conforming students, pursue their interests in technology. Pearl Hacks is a growing organization, looking for motivated students like you to take Pearl Hacks to new heights. Your work will directly impact the experience of hundreds of people from across the US. Learn more about our positions: https://bit.ly/PH24BOARD
In a programming assignment, you are asked to implement a function named subd (in python). The function’s parameters are of type list[str] and dict[str, int]. The purpose of the function is to return a new dictionary whose keys are the intersection of items in the list and keys in the dictionary parameter.
The resulting dictionary’s values are copies of the dictionary
parameter’s of the same key.
Example usage:
>>> subd(["a", "c", "d"], {"a": 1, "b": 2, "c": 3})
{"a": 1, "c": 3}
Consider these two ways to implement this function
def subd_v1(al: list[str], ad: dict[str, int]) -> dict[str, int]:
result: dict[str, int] = {}
for key in ad:
if key in al:
result[key] = ad[key]
return result
def subd_v2(al: list[str], ad: dict[str, int]) -> dict[str, int]:
result: dict[str, int] = {}
for key in al:
if key in ad:
result[key] = ad[key]
return result
Are these two functions equivalent? Is one as good as the other? Or would one be preferable over the other? Why, or why not?
Note that a dictionary in Python is a hashmap.
The result is a string of digits after the decimal point with the pattern
000 001 002 003 .... up to 999
except ...
^ 998
OK then, now try 1/9801
| Remember multiplying in school? Ever think about the worst-case time complexity of the method you learned? | |
|
You can think of integer arithmetic as a COMP-210-style ADT,
where the values of the type -- the values being operated on --
are the counting numbers,
and the operations of the type
are add, sub, div, mult, etc.
If you want to mult two numbers with D digits each,
what is O(mult), the worst
case time complexity to multiply?
|
|
mult(3282,7153) , in school we write it like this 3282
x 7153
------
|
|
1435982576992300100304459978286732198932032134405997828673219893203213440501 x 4359827576992333001003992300100304459978286732169899782867321989320321344 ---------------------------------------------------------------------------- mult( 1435982576992300100304459978286732198932032134405997828673219893203213440501 , 4359827576992333001003992300100304459978286732169899782867321989320321344 )We sharpen a box of pencils, get a loooong, wiiiiiddeeee piece of paper, and a vat of coffee, and settle in for a few days or weeks (well, really, we don't try to do this with our school-taught manual algorithm).
And then, what if we need to multiply two numbers with
a hundred thousand digits each?
Or a million digits each?
Processes in cryptography and security require this.
Now (in 2019) van der Hoven and Harvey have found an O(N log N) algorithm,
as proven to exist in 1971.
