bubble-sort.cppmath.cppmultithreading.cppnamespace.cppsignals.cppsmart-pointers.cppvectors.cpp
#include <iostream>
#include <vector>
constexpr void print_elements_in_vector(std::vector<int> numbers) {
for (int number : numbers) {
std::cout << number << std::endl;
}
}
int main() {
std::vector<int> numbers = { 14, 33, 27, 35, 10 };
// print unsorted
print_elements_in_vector(numbers); // 14 33 27 35 10
// bubble sort
for (int i = 0; i < numbers.size(); i++) {
for (int j = 0; j < numbers.size() - 1; j++) {
if (numbers[j] > numbers[j + 1]) {
int temp = numbers[j];
// swap positions
numbers[j] = numbers[j + 1];
numbers[j + 1] = temp;
}
}
}
// print sorted
print_elements_in_vector(numbers); // 10 14 27 33 35
}
#include <iostream>
#include <cmath>
int main() {
std::cout << INFINITY << std::endl; // inf
std::cout << NAN << std::endl; // nan
std::cout << isgreater(42, 10) << std::endl; // 1
std::cout << isless(42, 10) << std::endl; // 0
std::cout << isnan(NAN) << std::endl; // 1
std::cout << isinf(INFINITY) << std::endl; // 1
std::cout << isfinite(42) << std::endl; // 1
// trigonometric
std::cout << cos(42) << std::endl; // -0.399985
std::cout << sin(42) << std::endl; // -0.916522
std::cout << tan(42) << std::endl; // 2.29139
// exponential and logarithmic
std::cout << log10(10) << std::endl; // 1
std::cout << log2(8) << std::endl; // 3
std::cout << exp(2) << std::endl; // 7.38906
// binary exponential function
std::cout << exp2(2) << std::endl; // 4
// natural logarithm
std::cout << log(10) << std::endl; // 2.30259
// power and root
std::cout << pow(2, 3) << std::endl; // 8
std::cout << sqrt(16) << std::endl; // 4
std::cout << cbrt(27) << std::endl; // 3
// rounding and remainder
std::cout << ceil(41.5) << std::endl; // 42
std::cout << floor(42.5) << std::endl; // 42
std::cout << trunc(42.5) << std::endl; // 42
std::cout << round(41.5) << std::endl; // 42
std::cout << remainder(142, 100) << std::endl; // 42
// round to nearest integer
std::cout << rint(42.5) << std::endl; // 42
// round to nearby integer
std::cout << nearbyint(42.5) << std::endl; // 42
// manipulation
std::cout << copysign(42, -1) << std::endl; // -42
std::cout << nan("42") << std::endl; // nan
// minimum, maximum, difference
std::cout << fdim(52, 10) << std::endl; // 42
std::cout << fmax(42, 10) << std::endl; // 42
std::cout << fmin(42, 10) << std::endl; // 10
// absolute value (can handle floating-point)
std::cout << fabs(-12.5) << std::endl; // 12.5
// absolute value (only for integers)
std::cout << abs(-42) << std::endl; // 42
// fused multiply-add
std::cout << fma(42.5, 10, 200) << std::endl; // 625
}
#include <iostream>
#include <pthread.h>
constexpr int max_threads = 5;
void *print(void *thread_id) {
long tid = (long) thread_id;
std::cout << "thread_id: " << tid << std::endl;
// terminate
pthread_exit(NULL);
};
int main() {
pthread_t threads[max_threads];
int thread[max_threads];
for (int i = 0; i < max_threads; i++) {
thread[i] = i;
std::cout << "creating thread:" << thread[i] << std::endl;
// create thread using pthread_create(thread, attr, start_routine, arg)
if (pthread_create(&threads[i], NULL, print, (void*) &thread[i]) != 0) {
std::cout << "unable to create thread: " << thread << std::endl;
// fail
exit(-1);
}
}
// terminate
pthread_exit(NULL);
// creating thread:0
// creating thread:1
// thread_id: 140701949382784
// thread_id: 140701949382788
// creating thread:2
// creating thread:3
// thread_id: 140701949382792
// creating thread:4
// thread_id: 140701949382796
// thread_id: 140701949382800
}
#include <iostream>
// define namespace
namespace my_functions {
void function() {
std::cout << "called: my_functions::function" << std::endl;
}
}
int main() {
my_functions::function(); // called: my_functions::function
}
#include <iostream>
#include <csignal>
#include <unistd.h>
// signal handler
void terminate(int sig) {
std::cout << "\nsignal: " << sig << std::endl;
exit(sig);
}
int main() {
// register signal
signal(SIGINT, terminate);
// keyboard interrupt
while(1) {
std::cout << "stuck doing something really hard... (press ^C to exit)" << std::endl;
sleep(5);
}
// stuck doing something really hard... (press ^C to exit)
// ^C
// signal: 2
}
// smart pointers handle allocation and deletion of memory
#include <memory>
#include <iostream>
#include <vector>
class MyClass {
std::unique_ptr<std::vector<int>> data; // unique_ptr is a smart pointer
public:
MyClass(const int size) { data = std::make_unique<std::vector<int>>(size); } // allocate memory with make_unique
void print_data() {
for (auto i : *data) { std::cout << i << std::endl; }
}
};
void function_using_data() {
MyClass my_class(5); // lifetime tied to scope
my_class.print_data();
} // my_class is destroyed here
int main() {
function_using_data(); // 0 0 0 0 0
}
#include <iostream>
#include <vector>
#include <string>
#include <format>
int main() {
// vector of ints
std::vector<int> numbers;
// size
std::cout << numbers.size() << std::endl; // 0
// push values
for (int i = 1; i <= 5; i++) {
numbers.push_back(i);
}
std::cout << numbers.size() << std::endl; // 5
std::cout << numbers[3] << std::endl; // 4
// vector of strings
std::vector<std::string> strings = { "hello", "c++" };
std::cout << strings[0] << " " << strings[1] << std::endl; // hello c++
}
binary-search.cppfind-adjacent.cppfor-each.cpp
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> numbers = { 1, 2, 3, 4, 5 };
// binary_search
bool found = std::binary_search(numbers.begin(), numbers.end(), 4);
if (found) {
std::cout << "found value" << std::endl;
} else {
std::cout << "not found" << std::endl;
}
// found value
}
#include <algorithm>
#include <vector>
#include <iostream>
bool twice (int a, int b) { return a * 2 == b; }
int main() {
std::vector<int> numbers = { 50, 40, 10, 20, 20 };
// adjacent_find
auto iter = std::adjacent_find(numbers.begin(), numbers.end(), twice);
if (iter != numbers.end()) {
std::cout << *iter << ", " << *(iter + 1) << std::endl;
} else {
std::cout << "no adjacent pairs" << std::endl;
}
// 10, 20
}
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> numbers = { 1, 2, 3, 4, 5 };
// multiply each element in numbers using for_each
std::for_each(numbers.begin(), numbers.end(), [](int &number) {
number *= 2;
});
// for_each
std::for_each(numbers.begin(), numbers.end(), [](int number) {
std::cout << number << std::endl;
});
// 2 4 6 8 10
}
alu-in-python.pybubble-sort.pycombinations-with-replacement.pycomposing-functions.pyenumerate.pyerlang-b-formula.pyforeign-function-library.pyfunction-wrappers.pyfunctools-cache.pyglide-typing-problem.pylinked-list-using-recordclass.pynumpy-operators.pypandas-operators.pypartial-functions.pyregular-expression.pysobel-filter-using-opencl.py
"""
An ALU is a combinational logic circuit that performs
arithmetic and bitwise operations on input bits. This
is a 16-bit implementation.
"""
# binary to signed decimal
def binary_to_signed(lst):
binary_str = ''.join(map(str, lst))
if (binary_str[0] == '1'):
# invert bits
inverted_str = ''.join(['1' if c == '0' else '0' for c in binary_str[1:]])
decimal = -int(inverted_str, 2) - 1
else:
decimal = int(binary_str, 2)
return decimal
assert binary_to_signed([1,1,1,1,1,1,1,1]) == -1
# https://en.wikipedia.org/wiki/Two%27s_complement
def twos_complement_addition(a, b):
# convert to binary strings
a_bin = ''.join(map(str, a))
b_bin = ''.join(map(str, b))
# number of bits
bits = max(len(a_bin), len(b_bin))
# convert to twos complement
a_twos = int(a_bin, 2)
b_twos = int(b_bin, 2)
# addition
result_twos = a_twos + b_twos
# convert result to binary string
result = bin(result_twos & (2 ** bits - 1))[2:]
# convert result to list of ints
result = list(map(int, result))
# padding (if needed)
if (len(result) < bits):
# insert 0s to front
for bit in range(bits - len(result)): result.insert(0, 0)
return list(map(int, result))
assert twos_complement_addition([0,1,0,1], [0,1,0,1]) == [1,0,1,0]
"""
if (zx == 1) set x = 0 : 16-bit
if (nx == 1) set x = ~x : 16-bit bitwise not
if (zy == 1) set y = 0 : 16-bit constant
if (ny == 1) set y = ~y : 16-bit bitwise not
if (f == 1) set out = x + y : 16-bit twos complement addition
if (f == 0) set out = x & y : 16-bit bitwise and
if (no == 1) set out = ~out : 16-bit bitwise not
if (out == 0) set zr = 1 : 1-bit
if (out < 0) set ng = 1 : 1-bit
"""
def ALU(x, y, zx=0, nx=0, zy=0, ny=0, f=0, no=0):
"""
x : input x : 16-bit
y : input y : 16-bit
zx : zero x : 1-bit
nx : negate x : 1-bit
zy : zero y : 1-bit
ny : negate y : 1-bit
f : function : 1-bit
no : negate out : 1-bit
"""
# init output
out = [0] * len(x)
zr=0
ng=0
# if (zx == 1) set x = 0
if zx == 1:
for i in range(len(x)):
x[i] = 0
# if (nx == 1) set x = ~x
if nx == 1:
for i in range(len(x)):
if x[i] == 1: x[i] = 0
else: x[i] = 1
# if (zy == 1) set y = 0
if zy == 1:
for i in range(len(y)):
y[i] = 0
# if (ny == 1) set y = ~y
if ny == 1:
for i in range(len(y)):
if y[i] == 1: y[i] = 0
else: y[i] = 1
# if (f == 1) set out = x + y
if f == 1: out = twos_complement_addition(x, y)
# if (f == 0) set out = x & y
if f == 0:
for i in range(len(x)):
if x[i] and y[i]: out[i] = 1
else: out[i] = 0
# if (no == 1) set out = ~out
if no == 1:
for i in range(len(out)):
if out[i] == 1: out[i] = 0
else: out[i] = 1
# if (out == 0) set zr = 1
if all(bit == 0 for bit in out): zr = 1
# if (out < 0) set ng = 1
if binary_to_signed(out) < 0: ng = 1
return out, zr, ng
# test cases
"""
| x | y |zx|nx|zy|ny|f|no| out |zr|ng|
|0000000000000000|1111111111111111| 1| 0| 1| 0|1| 0|0000000000000000| 1| 0|
|0000000000000000|1111111111111111| 1| 1| 1| 1|1| 1|0000000000000001| 0| 0|
|0000000000000000|1111111111111111| 1| 1| 1| 0|1| 0|1111111111111111| 0| 1|
|0000000000000000|1111111111111111| 0| 0| 1| 1|0| 0|0000000000000000| 1| 0|
|0000000000000000|1111111111111111| 1| 1| 0| 0|0| 0|1111111111111111| 0| 1|
|0000000000000000|1111111111111111| 0| 0| 1| 1|0| 1|1111111111111111| 0| 1|
|0000000000000000|1111111111111111| 1| 1| 0| 0|0| 1|0000000000000000| 1| 0|
|0000000000000000|1111111111111111| 0| 0| 1| 1|1| 1|0000000000000000| 1| 0|
|0000000000000000|1111111111111111| 1| 1| 0| 0|1| 1|0000000000000001| 0| 0|
|0000000000000000|1111111111111111| 0| 1| 1| 1|1| 1|0000000000000001| 0| 0|
|0000000000000000|1111111111111111| 1| 1| 0| 1|1| 1|0000000000000000| 1| 0|
|0000000000000000|1111111111111111| 0| 0| 1| 1|1| 0|1111111111111111| 0| 1|
|0000000000000000|1111111111111111| 1| 1| 0| 0|1| 0|1111111111111110| 0| 1|
|0000000000000000|1111111111111111| 0| 0| 0| 0|1| 0|1111111111111111| 0| 1|
|0000000000000000|1111111111111111| 0| 1| 0| 0|1| 1|0000000000000001| 0| 0|
|0000000000000000|1111111111111111| 0| 0| 0| 1|1| 1|1111111111111111| 0| 1|
|0000000000000000|1111111111111111| 0| 0| 0| 0|0| 0|0000000000000000| 1| 0|
|0000000000000000|1111111111111111| 0| 1| 0| 1|0| 1|1111111111111111| 0| 1|
|0000000000010001|0000000000000011| 1| 0| 1| 0|1| 0|0000000000000000| 1| 0|
|0000000000010001|0000000000000011| 1| 1| 1| 1|1| 1|0000000000000001| 0| 0|
|0000000000010001|0000000000000011| 1| 1| 1| 0|1| 0|1111111111111111| 0| 1|
|0000000000010001|0000000000000011| 0| 0| 1| 1|0| 0|0000000000010001| 0| 0|
|0000000000010001|0000000000000011| 1| 1| 0| 0|0| 0|0000000000000011| 0| 0|
|0000000000010001|0000000000000011| 0| 0| 1| 1|0| 1|1111111111101110| 0| 1|
|0000000000010001|0000000000000011| 1| 1| 0| 0|0| 1|1111111111111100| 0| 1|
|0000000000010001|0000000000000011| 0| 0| 1| 1|1| 1|1111111111101111| 0| 1|
|0000000000010001|0000000000000011| 1| 1| 0| 0|1| 1|1111111111111101| 0| 1|
|0000000000010001|0000000000000011| 0| 1| 1| 1|1| 1|0000000000010010| 0| 0|
|0000000000010001|0000000000000011| 1| 1| 0| 1|1| 1|0000000000000100| 0| 0|
|0000000000010001|0000000000000011| 0| 0| 1| 1|1| 0|0000000000010000| 0| 0|
|0000000000010001|0000000000000011| 1| 1| 0| 0|1| 0|0000000000000010| 0| 0|
|0000000000010001|0000000000000011| 0| 0| 0| 0|1| 0|0000000000010100| 0| 0|
|0000000000010001|0000000000000011| 0| 1| 0| 0|1| 1|0000000000001110| 0| 0|
|0000000000010001|0000000000000011| 0| 0| 0| 1|1| 1|1111111111110010| 0| 1|
|0000000000010001|0000000000000011| 0| 0| 0| 0|0| 0|0000000000000001| 0| 0|
|0000000000010001|0000000000000011| 0| 1| 0| 1|0| 1|0000000000010011| 0| 0|
"""
with open("_alu_tests.txt", "r") as tests:
for test in tests.read().split('\n')[1:]:
test = test.split('|')[1:-1]
values = [col.strip() for col in test]
out, zr, ng = ALU(
# input x
list(map(int, list(values[0]))),
# input y
list(map(int, list(values[1]))),
# control bits
zx=int(values[2]),
nx=int(values[3]),
zy=int(values[4]),
ny=int(values[5]),
f=int(values[6]),
no=int(values[7])
)
assert out == list(map(int, list(values[8])))
assert zr == int(values[9])
assert ng == int(values[10])
# https://en.wikipedia.org/wiki/Bubble_sort
unsorted_list = [14, 33, 27, 35, 10]
for i in range(len(unsorted_list)):
for j in range(len(unsorted_list) - 1):
if unsorted_list[j] > unsorted_list[j + 1]:
temp = unsorted_list[j]
# swap
unsorted_list[j] = unsorted_list[j + 1]
unsorted_list[j + 1] = temp
print(unsorted_list) # [10, 14, 27, 33, 35]
from itertools import combinations_with_replacement
my_list = ['A', 'B']
combinations = []
for item in list(range(len(my_list))):
combinations.append(list(combinations_with_replacement(my_list, item + 1)))
print(combinations)
# [[('A',), ('B',)], [('A', 'A'), ('A', 'B'), ('B', 'B')]]
# flatten
combinations = [a for b in combinations for a in b]
print(combinations)
# [('A',), ('B',), ('A', 'A'), ('A', 'B'), ('B', 'B')]
import functools
import operator
def compose(a, b): return lambda x: a(b(x))
def square(x): return x * x
def double(x): return x * 2
# double then square
op = compose(square, double)
print(op(5)) # 100
# passing operator as argument
numbers = [1, 2, 3, 4, 5]
print(functools.reduce(operator.add, numbers)) # 15
my_list = ["Zero", "One", "Two", "Three", "Four", "Five"]
for item in enumerate(my_list): print(item)
# (0, 'First')
# (1, 'Second')
# (2, 'Third')
# (3, 'Fourth')
# (4, 'Fifth')
# https://en.wikipedia.org/wiki/Erlang_(unit)#Erlang_B_formula
from math import factorial
def erlang(A, m):
L = (A ** m) / factorial(m)
sum_ = 0
for n in range(m + 1): sum_ += (A ** n) / factorial(n)
return (L / sum_)
print(erlang(90, 107)) # 0.008799105244742682
"""
A foreign function library is a library written in
languages other than the language it is being called
from. E.g., a Python program calling function from C
library.
"""
"""
// _square.c
#include <stdio.h>
int square(int num) {
return num * num;
}
// compile into shared library:
// $ gcc -shared -o _square.so -fPIC _square.c
"""
import ctypes
# load the shared library
square_lib = ctypes.CDLL('./_square.so')
# specify function return and argument types
square_lib.square.restype = ctypes.c_int
square_lib.square.argtypes = [ctypes.c_int]
# call the foreign function
num = 5
result = square_lib.square(num)
print(f"the square of {num} is {result}")
# the square of 5 is 25
# using C standard library functions
# https://gist.github.com/PewZ/8b473c2a6888c5c528635550d07c6186
libc = ctypes.CDLL('libc.dylib')
libc.printf(b"hello world\n") # hello world
"""
Function wrappers can be used to modify behavior of function
or method. The wraps decorator copies over the function name,
docstring, and arguments list to the wrapper function. This
is very useful for debugging and logging.
"""
from functools import wraps
def logging(func):
@wraps(func)
def wrapper(*args, **kwargs):
print(f"call to {func.__name__}, args: {args}, kwargs: {kwargs}")
return func(*args, **kwargs)
return wrapper
@logging
def power(base, exp): return base ** exp
power(2, 3) # call to power, args: (2, 3), kwargs: {}
"""
The lru_cache decorator caches the results of a function
call with a given set of arguments. This is useful for
functions that are computationally expensive and have a
limited set of arguments.
"""
from functools import lru_cache
import timeit
def fib(n): return n if n < 2 else fib(n - 1) + fib(n - 2)
# fibonacci with cache
@lru_cache(maxsize=128)
def fib_cache(n): return n if n < 2 else fib_cache(n - 1) + fib_cache(n - 2)
print(format(timeit.timeit('fib(30)', globals=globals(), number=1), '.17f'))
# 0.12468479387462139
print(format(timeit.timeit('fib_cache(30)', globals=globals(), number=1), '.17f'))
# 0.00001071766018867
print(fib_cache.cache_info())
# CacheInfo(hits=28, misses=31, maxsize=128, currsize=31)
"""
Glide typing is the feature on mobile devices that allows
users to type by swiping across the keyboard. The keyboard
will predict the word based on the path of the swipe.
"""
input_ = "hgferyjkllkop"
words = ["coffee", "coding", "happy", "hello", "hop"]
chars = list(input_)
matches = []
for word in words:
cidx = 0
col = 0
while col < len(chars):
# print(chars[col], col)
if chars[col] == word[cidx]:
cidx += 1
if cidx == len(word):
matches.append((word, col))
break
col += 1
# all matches
print(matches) # [('hello', 11), ('hop', 12)]
# first match
print(matches[0][0]) # hello
"""
A linked list is a linear data structure where each element
is the data and reference to next element. The last element
reference to None and an empty linked list has a None head.
"""
from recordclass import recordclass
# recordclass is a mutable namedtuple
Element = recordclass("Element", ["value", "next"])
class LinkedList:
# linked list constructor
def __init__(self): self.head = None
# string representation of linked list
def __str__(self):
if self.head is None: return "[]"
current = self.head
values = []
while current is not None:
values.append(current.value)
current = current.next
return str(values)
# insert element at tail
def insert(self, value):
# insert at head
if self.head is None: self.head = Element(value, None)
else:
current = self.head
# iterate until last element
while current.next is not None: current = current.next
# insert element
current.next = Element(value, None)
# remove element
def remove(self, value):
# remove head
if self.head.value == value: self.head = self.head.next
else:
current = self.head
# iterate until last element
while current.next is not None:
# remove element if found
if current.next.value == value:
current.next = current.next.next
return
current = current.next
ll = LinkedList()
ll.insert(5)
ll.insert(10)
ll.insert(15)
ll.insert(20)
ll.insert(25)
ll.insert(30)
print(ll) # [5, 10, 15, 20, 25, 30]
ll.remove(15)
ll.remove(30)
print(ll) # [5, 10, 20, 25]
import numpy as np
# numpy array basics
a = [60, 28, 49, 81]
b = [55, 634, 704, 2020]
A = np.array(a, dtype='i') # [60 28 49 81]
AB = np.array([a, b])
# [[ 60 28 49 81]
# [ 55 634 704 2020]]
print(AB.ndim) # 2
print(AB.shape) # (2, 4)
arr_zero = np.zeros(4) # [0. 0. 0. 0.]
arr_ones = np.ones((2, 3))
# [[ 1. 1. 1.]
# [ 1. 1. 1.]]
arr_range = np.arange(0, 10)
# [0 1 2 3 4 5 6 7 8 9]
arr_linspace = np.linspace(0, 1, 5)
# [0. 0.25 0.5 0.75 1. ]
arr_log = np.logspace(0, 1, 5)
# [ 1. 1.77827941 3.16227766 5.62341325 10. ]
# slicing
print(A[1:3])
# [28 49]
print(AB[0:2, 2:4])
# [[ 49 81]
# [ 704 2020]]
# reverse order
print(A[::-1]) # [81 49 28 60]
print(arr_range.mean()) # 4.5
print(arr_range.sum()) # 45
print(AB.min()) # 28
print(AB.max()) # 2020
print(np.sin(AB))
# [[-0.30481062 0.27090579 -0.95375265 -0.62988799]
# [-0.99975517 -0.56605794 0.27947339 0.04406199]]
print(np.multiply(a, b))
# [ 3300 17752 34496 163620]
print(np.sqrt(b))
# [ 7.41619849 25.17935662 26.53299832 44.94441011]
# min value in each column
print(np.minimum(a, b)) # [55 28 49 81]
# sum of axis (columns)
print(np.sum(AB, axis=1)) # [ 218 3413]
# numpy indexing
# create array with 8 integers
A = 2 * np.arange(8)**2 + 1
# [ 1 3 9 19 33 51 73 99]
# create array with 16 integers
B = np.arange(16)
B.shape = (4, 4)
# [[ 0 1 2 3]
# [ 4 5 6 7]
# [ 8 9 10 11]
# [12 13 14 15]]
print(A[[3, -1, 1]])
# [19 99 3]
print(B[:, [2, -1, 0]])
# [[ 2 3 0]
# [ 6 7 4]
# [10 11 8]
# [14 15 12]]
# elements from A at indices given by fibonacci sequence
fibseq = np.array([0, 1, 1, 2, 3])
print(A[fibseq]) # [ 1 3 3 9 19]
# diagonal
i = np.arange(4)
print(B[i, i]) # [ 0 5 10 15]
# diagonal of part
print(B[i[:3], i[:3] + 1]) # [ 1 6 11]
# numpy masking
# create array with 16 integers
C = np.arange(16)
C.shape = (4, 4)
# [[ 0 1 2 3]
# [ 4 5 6 7]
# [ 8 9 10 11]
# [12 13 14 15]]
# create mask with True
mask = np.ones(4, dtype=bool) # [ True True True True]
# diagonal
print(C[mask, mask]) # [ 0 5 10 15]
# conditional mask
conditional = (C >= 9)
print(C[conditional]) # [ 9 10 11 12 13 14 15]
# get all values smaller than 9
print(C[C < 9]) # [0 1 2 3 4 5 6 7 8]
# get all values smaller than 5 or larger than 10
print(C[(C < 5) | (C > 10)])
# [ 0 1 2 3 4 11 12 13 14 15]
# where
print(C[np.where(C > 10)]) # [11 12 13 14 15]
# get all columns with a value less than 3
print(C[:, np.where(C < 3)[1]])
# [[ 0 1 2]
# [ 4 5 6]
# [ 8 9 10]
# [12 13 14]]
# numpy operations
A = np.arange(6) # [0 1 2 3 4 5]
print(A + A) # [ 0 2 4 6 8 10]
print(A - 1) # [-1 0 1 2 3 4]
print(A * 6) # [ 0 6 12 18 24 30]
# gradient
X = np.array([2, 4, 5])
Y = np.array([6, 2, 8])
print(np.gradient(X))
# [ 2. 1.5 1. ] => (4 - 2) / 1, (5 - 2) / 2, (5 - 4)/ 1
print(np.gradient(Y))
# [-4. 1. 6.] => (2 - 6) / 1, (8 - 6) / 2, (8 - 2)/ 1
# numerical derivative
print(np.gradient(Y) / np.gradient(X))
# [-2. 0.66666667 6. ]
B = np.arange(4)
B.shape = (2, 2)
# [[0 1]
# [2 3]]
v = np.array([[2],[4]])
# [[2]
# [4]]
# scalar (multiplication)
print(B * v)
# [[ 0 2]
# [ 8 12]]
# dot product
print(np.dot(B, v))
# [[ 4]
# [16]]
# operations on higher dimensions
M = np.arange(12)
M.shape = (4, 3)
# [[ 0 1 2]
# [ 3 4 5]
# [ 6 7 8]
# [ 9 10 11]]
v = np.array([16, 17, 18])
print(M + v)
# [[16 18 20]
# [19 21 23]
# [22 24 26]
# [25 27 29]]
import pandas as pd
# creating series (one-dimensional array)
simple_series = pd.Series([42, 55, 73], dtype='f8')
# 0 42.0
# 1 55.0
# 2 73.0
# dtype: float64
# creating series with specified index
index_series = pd.Series([42, 55, 73], index=["electron", "proton", "neutron"], dtype='f8')
# electron 42.0
# proton 55.0
# neutron 73.0
# dtype: float64
# accessing value in series
print(index_series["electron"])
# 42.0
# accessing multiple values in series (range)
print(index_series["electron":"neutron"])
# electron 42.0
# proton 55.0
# neutron 73.0
# dtype: float64
# accessing multiple values in series using indexing
print(index_series[1:])
# proton 55.0
# neutron 73.0
# dtype: float64
# creating series from dictionary
dict_series = pd.Series({ "electron": 6, "neutron": 28, "proton": 496, "neutrino": 8128 })
# electron 6
# neutrino 8128
# neutron 28
# proton 496
# dtype: int64
# combining two series into one column
print(index_series + dict_series)
# electron 48.0
# neutrino NaN
# neutron 101.0
# proton 551.0
# dtype: float64
# combining two series as dataframe
combined_series = pd.DataFrame({ "A": index_series, "B": dict_series })
# A B
# electron 42.0 6
# neutrino NaN 8128
# neutron 73.0 28
# proton 55.0 496
# accessing columns as series
print(combined_series["A"])
# electron 42.0
# neutrino NaN
# neutron 73.0
# proton 55.0
# Name: A, dtype: float64
# add new row with index
append_series = combined_series._append(pd.DataFrame({ "A": [-8128] }, index=["antineutrino"]))
# A B
# electron 42.0 6.0
# neutrino NaN 8128.0
# neutron 73.0 28.0
# proton 55.0 496.0
# antineutrino -8128.0 NaN
# drop row
append_series = append_series.drop("neutron")
# A B
# electron 42.0 6.0
# neutrino NaN 8128.0
# proton 55.0 496.0
# antineutrino -8128.0 NaN
# transpose
print(combined_series.T)
# electron neutrino neutron proton
# A 42.0 NaN 73.0 55.0
# B 6.0 8128.0 28.0 496.0
# masking
print(combined_series > 120)
# A B
# electron False False
# neutrino False True
# neutron False False
# proton False True
# add masking as column (e.g. larger than 120)
combined_series["large"] = (combined_series["A"] > 120) | (combined_series["B"] > 120)
# A B large
# electron 42.0 6 False
# neutrino NaN 8128 True
# neutron 73.0 28 False
# proton 55.0 496 True
# delete a column
del combined_series["large"]
# A B
# electron 42.0 6
# neutrino NaN 8128
# neutron 73.0 28
# proton 55.0 496
"""
A partial function is a function with some arguments already
filled in. This is useful for creating new functions from
existing functions.
"""
from functools import partial
def power(base, exp): return base ** exp
# partial functions
square = partial(power, exp=2)
cube = partial(power, exp=3)
print(square(2)) # 4
print(cube(2)) # 8
# partial functions with map
numbers = [1, 2, 3, 4, 5]
print(list(map(square, numbers)))
# [1, 4, 9, 16, 25]
print(list(map(cube, numbers)))
# [1, 8, 27, 64, 125]
import re
text = "some random text to test regular expressions"
date = "2017-07-16"
# create pattern -> four letter word ending with "st"
pattern_text = "..st"
pattern = re.compile(pattern_text)
# search for pattern in text
re_search = re.search(pattern, text)
if (re_search): print(re_search.group()) # test
# separate text
print(re.split(pattern, text))
# ['some random text to ', ' regular expressions']
# substitute word in text
print(re.sub(pattern, "learn", text, 1))
# some random text to learn regular expressions
# match
print(re.match("20[01][0-9].*[0-9][0-9].*[0-9][0-9]", date) != None)
# True
"""
A Sobel filter is an edge detection filter. It's a 3x3
convolution commonly used in image processing.
"""
import numpy as np
import pyopencl as cl
from PIL import Image, ImageFilter
# load image
input_image = Image.open('_images/photo.png').convert('L')
input_array = np.array(input_image).astype(np.uint8)
# input_image.show()
# sobel kernel
# sobel_x_kernel = np.array([[-1, 0, 1], [-2, 0, 2], [-1, 0, 1]]).astype(np.float32)
# sobel_y_kernel = np.array([[-1, -2, -1], [0, 0, 0], [1, 2, 1]]).astype(np.float32)
# opencl
platform = cl.get_platforms()[0]
device = platform.get_devices()[2] # AMD Radeon Pro 5500M Compute Engine
ctx = cl.Context([device])
queue = cl.CommandQueue(ctx)
# buffers
input_buffer = cl.Buffer(ctx, cl.mem_flags.READ_ONLY | cl.mem_flags.COPY_HOST_PTR, hostbuf=input_array)
output_buffer = cl.Buffer(ctx, cl.mem_flags.WRITE_ONLY, input_array.nbytes)
# compile kernel
program = cl.Program(ctx, """
__kernel void sobel_filter(__global const uchar* input, __global uchar* output, const int width, const int height) {
int x = get_global_id(0);
int y = get_global_id(1);
if (x > 0 && x < width - 1 && y > 0 && y < height - 1) {
float sum_x = 0;
float sum_y = 0;
const float sobel_x_kernel[3][3] = { {-1, 0, 1}, {-2, 0, 2}, {-1, 0, 1} };
const float sobel_y_kernel[3][3] = { {-1, -2, -1}, {0, 0, 0}, {1, 2, 1} };
for (int i = -1; i <= 1; ++i) {
for (int j = -1; j <= 1; ++j) {
sum_x += input[(y + i) * width + (x + j)] * sobel_x_kernel[i + 1][j + 1];
sum_y += input[(y + i) * width + (x + j)] * sobel_y_kernel[i + 1][j + 1];
}
}
float gradient_magnitude = sqrt(sum_x * sum_x + sum_y * sum_y);
gradient_magnitude = gradient_magnitude > 255 ? 255 : gradient_magnitude;
output[y * width + x] = (uchar)gradient_magnitude;
} else {
output[y * width + x] = 0;
}
}
""").build()
program.sobel_filter(queue, input_array.shape, None, input_buffer, output_buffer, np.int32(input_array.shape[1]), np.int32(input_array.shape[0]))
# read result
output_array = np.empty_like(input_array)
cl.enqueue_copy(queue, output_array, output_buffer).wait()
# save image
output_image = Image.fromarray(output_array, 'L')
output_image.save('_images/edges.png')
# show image
# output_image.show()
genetic-algorithm-optimization.pyparticle-swarm-optimisation.py
# https://en.wikipedia.org/wiki/Genetic_algorithm
import random
import math
# https://pypi.org/project/tabulate/
from tabulate import tabulate
random.seed(42)
# helper function to print as table
def print_as_table(population):
table = tabulate(
population,
headers=['n', 'encoding', 'decoded x, y', 'cost'],
floatfmt=".3f",
tablefmt="simple"
)
print(table, end="\n\n")
def encode(x, x_low, x_high, m):
"""Encode decimal number into binary
x (int) : decimal number
x_low (int) : lower bound of x
x_high (int) : upper bound of x
m (int) : number of bits
"""
decimal = round((x - x_low) / ((x_high - x_low) / (2 ** m - 1)))
binary = []
while decimal >= 1:
if decimal % 2 == 1:
binary.append(1)
else:
binary.append(0)
decimal = math.floor(decimal / 2)
while len(binary) < 4:
binary.append(0)
return list(reversed(binary))
assert encode(9, -10, 14, 5) == [1, 1, 0, 0, 1]
def decode(B, x_low, x_high, m):
"""Decode binary into decimal number
B (list) : binary number
x_low (int) : lower bound of x
x_high (int) : upper bound of x
m (int) : number of bits
"""
return x_low + int((''.join(map(str, B))), 2) * ((x_high - x_low) / ((2 ** m) - 1))
assert int(decode([1, 1, 0, 0, 1], -10, 14, 5)) == 9
def generate_population(f, n_pop, x_range, y_range, m_bits):
"""Generate initial population
f (function) : cost function
n_pop (int) : number of population
x_range (list) : range of x
y_range (list) : range of y
m_bits (int) : number of bits
"""
pop_lst = []
for i in range(n_pop):
x = random.randint(x_range[0], x_range[1])
y = random.randint(y_range[0], y_range[1])
# encoded values
x_encoded = encode(x, x_range[0], x_range[1], m_bits)
y_encoded = encode(y, y_range[0], y_range[1], m_bits)
# decoded values
x_decoded = round(decode(x_encoded, x_range[0], x_range[1], m_bits), 2)
y_decoded = round(decode(y_encoded, y_range[0], y_range[1], m_bits), 2)
# determine initial cost
cost = round(f(x_decoded, y_decoded), 2)
# append to list
pop_lst.append([i, x_encoded + y_encoded, [x_decoded, y_decoded], cost])
# sort on cost
pop_lst.sort(key = lambda x: x[3])
# update index
for i in range(len(pop_lst)):
pop_lst[i][0] = i
return pop_lst
# example_population = generate_population(
# f,
# n_pop=6,
# x_range=[5, 20],
# y_range=[-5, 15],
# m_bits=4
# )
# print_as_table(example_population)
# n encoding decoded x, y cost
# --- ------------------------ -------------- -------
# 0 [0, 0, 1, 0, 1, 1, 1, 0] [7.0, 13.67] 22.160
# 1 [0, 0, 1, 1, 1, 1, 0, 1] [8.0, 12.33] 30.680
# 2 [0, 0, 1, 1, 0, 0, 0, 0] [8.0, -5.0] 100.000
# 3 [1, 0, 0, 0, 0, 1, 0, 1] [13.0, 1.67] 119.140
# 4 [0, 1, 1, 1, 0, 0, 1, 1] [12.0, -1.0] 126.000
# 5 [1, 1, 0, 1, 0, 0, 0, 1] [18.0, -3.67] 213.030
def generate_offsprings(population, crossover):
"""Generate offsprings
population (list) : population
crossover (list) : crossover points
"""
n = 0
offsprings_lst = []
while n < len(population):
offsprings_lst.append(
population[n][1][0:crossover[0]] +
population[n + 1][1][crossover[0]:crossover[1]] +
population[n][1][crossover[1]:]
)
offsprings_lst.append(
population[n + 1][1][0:crossover[0]] +
population[n][1][crossover[0]:crossover[1]] +
population[n + 1][1][crossover[1]:]
)
# pair-wise
n += 2
return offsprings_lst
def mutate(offsprings, mu, m_bits):
"""Mutate offsprings
offsprings (list) : offsprings
mu (float) : mutation rate
m_bits (int) : number of bits
"""
nbits = round(mu * (len(offsprings) * m_bits * 2))
for i in range(nbits):
offspring = random.randint(0, len(offsprings) - 1)
bit = random.randint(0, m_bits * 2 - 1)
# flip bits
if offsprings[offspring][bit] == 1:
offsprings[offspring][bit] = 0
else:
offsprings[offspring][bit] = 1
return offsprings
def update_population(f, current_population, offsprings, keep, x_range, y_range, m_bits):
"""Update population
f (function) : cost function
current_population (list) : current population
offsprings (list) : offsprings
keep (int) : number of population to keep
x_range (list) : range of x
y_range (list) : range of y
m_bits (int) : number of bits
"""
offsprings_lst = []
for i in range(len(offsprings)):
# decoded values
x_decoded = round(decode(offsprings[i][:4], x_range[0], x_range[1], m_bits), 2)
y_decoded = round(decode(offsprings[i][4:], y_range[0], y_range[1], m_bits), 2)
# determine initial cost
cost = round(f(x_decoded, y_decoded), 2)
# append to list
offsprings_lst.append([i, offsprings[i], [x_decoded, y_decoded], cost])
# sort on cost
offsprings_lst.sort(key = lambda x: x[3])
# update index
for i in range(len(offsprings_lst)):
offsprings_lst[i][0] = i
# discard current population
current_population[keep:] = offsprings_lst[:keep]
# sort on cost
current_population.sort(key = lambda x: x[3])
# update index
for i in range(len(current_population)):
current_population[i][0] = i
return current_population
M_BITS = 4
N_POP = 4
N_KEEP = 2
MUTATE_RATE = 0.1
# max number of generations
MAX_GEN = 10000
# crossover points
crossover = [3, 6]
# cost function to minimize
def f(x, y): return -x * ((y / 2) - 10)
# bounds
x_range = [10, 20]
y_range = [-5, 7]
current_population = generate_population(f, N_POP, x_range, y_range, M_BITS)
print_as_table(current_population)
# n encoding decoded x, y cost
# --- ------------------------ -------------- -------
# 0 [0, 0, 0, 0, 1, 1, 1, 0] [10.0, 6.2] 69.000
# 1 [0, 1, 0, 0, 0, 0, 1, 0] [12.67, -3.4] 148.240
# 2 [0, 1, 1, 0, 0, 1, 0, 0] [14.0, -1.8] 152.600
# 3 [1, 1, 1, 1, 0, 0, 0, 1] [20.0, -4.2] 242.000
for i in range(MAX_GEN):
# generate offsprings
offsprings = generate_offsprings(current_population, crossover)
# mutate
offsprings = mutate(offsprings, MUTATE_RATE, M_BITS)
# update population
current_population = update_population(
f,
current_population,
offsprings,
N_KEEP,
x_range,
y_range,
M_BITS
)
print_as_table(current_population)
# n encoding decoded x, y cost
# --- ------------------------ -------------- ------
# 0 [0, 0, 0, 0, 1, 1, 1, 1] [10.0, 7.0] 65.000
# 1 [0, 0, 0, 0, 1, 1, 1, 1] [10.0, 7.0] 65.000
# 2 [0, 0, 0, 0, 1, 1, 1, 1] [10.0, 7.0] 65.000
# 3 [0, 0, 0, 0, 1, 1, 1, 1] [10.0, 7.0] 65.000
# https://en.wikipedia.org/wiki/Particle_swarm_optimization
import random
random.seed(42)
# feel free to change this to stop at convergence
MAX_ITERATIONS = 50
# constant inertia weight
weight = 0.5
# cognative constant
c_1 = 1
# social constant
c_2 = 2
def generate_swarm(x_0, n_par):
"""Generate swarm of particles
x_0 (list) : initial position
n_par (int) : number of particles
"""
dimensions = len(x_0)
swarm = []
# generate particles
for i in range(0, n_par):
position = []
# best position
position_best = -1
# particle velocity
velocity = []
# particle error (cost)
error = -1
# best error (cost)
error_best = error
# position and velocity
for i in range(0, dimensions):
position.append(x_0[i])
velocity.append(random.uniform(-1, 1))
# append particle
swarm.append({
"dimensions": dimensions,
"position": position,
"position_best": position_best,
"velocity": velocity,
"error": error,
"error_best": error_best
})
return swarm
def update_velocity(velocity, position, position_best, global_pos):
"""Update particle velocity
velocity (float) : particle velocity
position (float) : particle position
position_best (float) : best position
global_pos (float) : global best position
"""
# random bias
r_1 = random.random()
r_2 = random.random()
# update velocity
velocity_cognative = c_1 * r_1 * (position_best - position)
velocity_social = c_2 * r_2 * (global_pos - position)
velocity = weight * velocity + velocity_cognative + velocity_social
return velocity
def update_position(position, velocity):
"""Update particle position
position (float) : particle position
velocity (float) : particle velocity
"""
position = position + velocity
return position
def iterate_swarm(f, swarm, bounds=None, global_best=-1, global_pos=-1):
"""Iterate swarm
f (function) : cost function
swarm (list) : list of particles
bounds (list) : list of bounds for each dimension
global_best (float) : global best error
global_pos (float) : global best position
"""
for j in range(0, len(swarm)):
dimensions = swarm[j]["dimensions"]
position = swarm[j]["position"]
error_best = swarm[j]["error_best"]
# evaluate new error (cost)
error = swarm[j]["error"] = f(position)
# update local best position if current position gives
# better local error
if (error < error_best or error_best == -1):
swarm[j]["position_best"] = position
swarm[j]["error_best"] = error
position_best = swarm[j]["position_best"]
velocity = swarm[j]["velocity"]
# update global best if position of current particle gives
# best global error
if (error < global_best or global_best == -1):
global_pos = list(position)
global_best = float(error)
# update particle velocity and position
for i in range(0, dimensions):
velocity[i] = update_velocity(
velocity[i],
position[i],
position_best[i],
global_pos[i]
)
position[i] = update_position(
position[i],
velocity[i]
)
# max value for position
if bounds and (position[i] > bounds[i][1]):
position[i] = bounds[i][1]
# min value for position
if bounds and (position[i] < bounds[i][0]):
position[i] = bounds[i][0]
# return
return swarm, round(global_best, 2), [round(pos, 2) for pos in global_pos]
# minimize x^5 - 3x^4 + 5 over [0, 4]
def f(x): return x[0] ** 5 - 3 * x[0] ** 4 + 5
# reset global
global_best = -1
global_pos = -1
# initial swarm
swarm = generate_swarm(x_0=[5], n_par=15)
# iterate swarm
for i in range(MAX_ITERATIONS):
swarm, global_best, global_pos = iterate_swarm(
f,
swarm,
bounds=[(0, 4)],
global_best=global_best,
global_pos=global_pos
)
assert (global_best, global_pos) == (-14.91, [2.39])
# minimize -(5 + 3x - 4y - x^2 + x y - y^2)
def f(x): return -(5 + 3 * x[0] - 4 * x[1] - x[0] ** 2 + x[0] * x[1] - x[1] ** 2)
# reset global
global_best = -1
global_pos = -1
# initial swarm
swarm = generate_swarm(x_0=[5, 5], n_par=15)
# iterate swarm
for i in range(MAX_ITERATIONS):
swarm, global_best, global_pos = iterate_swarm(
f,
swarm,
global_best=global_best,
global_pos=global_pos
)
assert (global_best, global_pos) == (-9.33, [0.67, -1.67])
backpropagation.pyconvolutional-neural-network.pydelta-learning-algorithm.pygradient-descent-algorithm.pyk-nearest-neighbors-classifier.pylinear-threshold-unit.pynumpy-linear-relu.pywidrow-hoff-learning-algorithm.py
# https://en.wikipedia.org/wiki/Backpropagation
import numpy as np
np.random.seed(42)
# https://en.wikipedia.org/wiki/Sigmoid_function
def sigmoid(x): return 1.0 / (1 + np.exp(-x))
assert(sigmoid(0) == 0.5)
# derivative of sigmoid
def sigmoid_dx(x): return x * (1.0 - x)
assert(sigmoid_dx(0.5) == 0.25)
# input
x = np.array([[0,0,1], [0,1,1], [1,0,1], [1,1,1]])
y = np.array([[0], [1], [1], [0]])
# weights
w_1 = np.random.rand(x.shape[1],4)
w_2 = np.random.rand(4,1)
# output
output = np.zeros(y.shape)
def feedforward(x, w_1, w_2, output):
layer_1 = sigmoid(np.dot(x, w_1))
output = sigmoid(np.dot(layer_1, w_2))
return layer_1, w_1, w_2, output
def backpropagation(layer_1, w_1, w_2, x, y, output):
w_2_dx = np.dot(
np.transpose(layer_1),
(2 * (y - output) * sigmoid_dx(output))
)
w_1_dx = np.dot(
np.transpose(x),
(np.dot(2 * (y - output) * sigmoid_dx(output), np.transpose(w_2)) * sigmoid_dx(layer_1))
)
# update weights
w_1 += w_1_dx
w_2 += w_2_dx
return layer_1, w_1, w_2, x, y, output
for i in range(1500):
layer_1, w_1, w_2, output = feedforward(x, w_1, w_2, output)
layer_1, w_1, w_2, x, y, output = backpropagation(layer_1, w_1, w_2, x, y, output)
print(output)
# [[0.01043733]
# [0.97230567]
# [0.97090151]
# [0.03501066]]
# https://en.wikipedia.org/wiki/Convolutional_neural_network
import os
import numpy as np
import matplotlib.pyplot as plt
from tensorflow.keras.datasets import mnist
from tensorflow.keras.models import Sequential, load_model
from tensorflow.keras.layers import Dense, Dropout, Flatten, Conv2D, MaxPooling2D
from tensorflow.keras.utils import to_categorical
from tqdm.keras import TqdmCallback
# avoid libiomp5 error and less noise
os.environ["KMP_DUPLICATE_LIB_OK"] = "True"
os.environ["CUDA_VISIBLE_DEVICES"] = ""
# configuration
batch_size = 128
n_classes = 10
epochs = 5
# https://keras.io/datasets
(X_train, Y_train), (X_test, Y_test) = mnist.load_data()
# reshape and set type
X_train = X_train.reshape(X_train.shape[0], 28, 28, 1)
X_test = X_test.reshape(X_test.shape[0], 28, 28, 1)
X_train = X_train.astype('float32')
X_test = X_test.astype('float32')
# normalize
X_train = X_train / 255
X_test = X_test / 255
# https://en.wikipedia.org/wiki/One-hot
Y_train = to_categorical(Y_train, n_classes)
Y_test = to_categorical(Y_test, n_classes)
# print(Y_train.shape)
# print(Y_test.shape)
# https://keras.io/models/sequential
model = Sequential()
# layers
model.add(Conv2D(filters=32, kernel_size=(5, 5), activation='relu', input_shape=(28, 28, 1)))
model.add(Conv2D(filters=64, kernel_size=(3, 3), activation='relu'))
model.add(MaxPooling2D(pool_size=(2, 2)))
model.add(Dropout(0.25))
model.add(Flatten())
model.add(Dense(n_classes, activation='relu'))
model.add(Dropout(0.5))
model.add(Dense(n_classes, activation='softmax'))
# https://keras.io/optimizers
model.compile(loss='categorical_crossentropy', metrics=['accuracy'], optimizer='adadelta')
# train model
model.fit(
X_train,
Y_train,
validation_data=(X_test, Y_test),
epochs=epochs,
batch_size=batch_size,
verbose=0,
callbacks=[TqdmCallback(verbose=1)]
)
# evaluate
metrics = model.evaluate(X_test, Y_test, verbose=2)
# metrics
loss = metrics[0]
accuracy = metrics[1]
print(loss) # 0.029002553918152263
print(accuracy) # 0.9906
# https://en.wikipedia.org/wiki/Delta_rule
import numpy as np
from tabulate import tabulate
# initial weights
w = [1, 0, 0]
# learning rate
n = 1
# iterations
iterations = 12
# dataset
X = [[1, 0, 2],
[1, 1, 2],
[1, 2, 1],
[1, -3, 1],
[1, -2, -1],
[1, -3, -2]]
# classes
t = [1, 1, 1, 0, 0, 0]
# https://en.wikipedia.org/wiki/Heaviside_step_function
def transfer_function(w, x):
wx = np.dot(w, x)
if (wx > 0):
return 1
elif (wx == 0):
return 0.5
else:
return 0
assert (transfer_function([0.1, -0.5, 0.4], [0.1, -0.5, 0.4]) == 1)
assert (transfer_function([0.1, -0.5, 0.4], [0.1, 0.5, 0.4]) == 0)
assert (transfer_function([0, 0, 0], [0, 0, 0]) == 0.5)
# sequential delta learning algorithm
result = []
for o in range(int(iterations / len(X))):
for i in range(len(X)):
if ((i + 1 + (len(X) * o)) > iterations): break
w_prev = w
x = X[i]
y = transfer_function(w, x)
# calculate update part
update = np.zeros(len(x))
for j in range(len(x)): update[j] = n * (t[i] - y) * x[j]
# add update part to w
w = np.add(w, update)
# append to result
result.append([
# iteration
i + 1 + (len(X) * o),
# w
list(w_prev),
# x
x,
# y = H(wx)
y,
# t
t[i],
# w_new
list(w)]
)
print(tabulate(result, headers=['i', 'w', 'x', 'y = H(wx)', 't', 'w_new'], tablefmt="simple"))
# i w x y = H(wx) t w_new
# --- ---------------- ----------- ----------- --- ----------------
# 1 [1, 0, 0] [1, 0, 2] 1 1 [1.0, 0.0, 0.0]
# 2 [1.0, 0.0, 0.0] [1, 1, 2] 1 1 [1.0, 0.0, 0.0]
# 3 [1.0, 0.0, 0.0] [1, 2, 1] 1 1 [1.0, 0.0, 0.0]
# 4 [1.0, 0.0, 0.0] [1, -3, 1] 1 0 [0.0, 3.0, -1.0]
# 5 [0.0, 3.0, -1.0] [1, -2, -1] 0 0 [0.0, 3.0, -1.0]
# 6 [0.0, 3.0, -1.0] [1, -3, -2] 0 0 [0.0, 3.0, -1.0]
# 7 [0.0, 3.0, -1.0] [1, 0, 2] 0 1 [1.0, 3.0, 1.0]
# 8 [1.0, 3.0, 1.0] [1, 1, 2] 1 1 [1.0, 3.0, 1.0]
# 9 [1.0, 3.0, 1.0] [1, 2, 1] 1 1 [1.0, 3.0, 1.0]
# 10 [1.0, 3.0, 1.0] [1, -3, 1] 0 0 [1.0, 3.0, 1.0]
# 11 [1.0, 3.0, 1.0] [1, -2, -1] 0 0 [1.0, 3.0, 1.0]
# 12 [1.0, 3.0, 1.0] [1, -3, -2] 0 0 [1.0, 3.0, 1.0]
# https://en.wikipedia.org/wiki/Gradient_descent
import numpy as np
import random
random.seed(42)
def gradient_descent(x, y, theta, alpha, m, num_iterations):
"""Gradient descent algorithm
x (numpy.ndarray) : input data
y (numpy.ndarray) : target variable
theta (numpy.ndarray) : parameters
alpha (float) : learning rate
m (int) : number of examples
num_iterations (int) : number of iterations
"""
x_transpose = x.transpose()
for i in range(0, num_iterations):
hypothesis = np.dot(x, theta)
loss = hypothesis - y
cost = np.sum(loss ** 2) / (2 * m)
# print
print("Iteration: %d, Cost: %f" % (i, cost))
# average gradient per example
gradient = np.dot(x_transpose, loss) / m
# update
theta = theta - alpha * gradient
return theta
def generate_data(num_points, bias, variance):
"""Generate data
num_points (int) : number of points
bias (int) : bias
variance (int) : variance
"""
x = np.zeros(shape=(num_points, 2))
y = np.zeros(shape=num_points)
# straight line
for i in range(0, num_points):
# bias feature
x[i][0] = 1
x[i][1] = 1
# target variable
y[i] = (i + bias) + random.uniform(0, 1) * variance
return x, y
# generate data
x, y = generate_data(100, 25, 10)
m, n = np.shape(x)
# configuration variables
num_iterations = 10000
alpha = 0.0005
theta = np.ones(n)
# run gradient descent
theta = gradient_descent(x, y, theta, alpha, m, num_iterations)
print(theta)
# Iteration: 0, Cost: 3417.449751
# Iteration: 1, Cost: 3411.478114
# Iteration: 2, Cost: 3405.518415
# ...
# Iteration: 9997, Cost: 430.137723
# Iteration: 9998, Cost: 430.137723
# Iteration: 9999, Cost: 430.137723
# [39.64610036 39.64610036]
# https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm
import numpy as np
from sklearn import datasets
from tabulate import tabulate
# load iris dataset
iris = datasets.load_iris()
# sample to test classifier
sample = np.array([
[1, 9, 0, 4, 5, 3, 2],
[9, 0, 4, 5, 3, 2, 1],
[0, 4, 5, 3, 2, 1, 9],
[4, 5, 3, 2, 1, 9, 0]
])
sample = sample / np.array([2.3, 4, 1.5, 4]).reshape(-1, 1)
sample = sample + np.array([4, 2, 1, 0]).reshape(-1, 1)
sample = sample.transpose()
# sklearn
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import classification_report, confusion_matrix, accuracy_score
# split training dataset
X_train, X_test, Y_train, Y_test = train_test_split(iris.data, iris.target, test_size=0.2)
# training and predictions
classifier = KNeighborsClassifier(n_neighbors=3, metric='euclidean')
classifier.fit(X_train, Y_train)
# evaluate
Y_prediction = classifier.predict(X_test)
# print(confusion_matrix(Y_test, Y_prediction))
print(classification_report(Y_test, Y_prediction))
# precision recall f1-score support
# 0 1.00 1.00 1.00 11
# 1 0.91 0.91 0.91 11
# 2 0.88 0.88 0.88 8
# accuracy 0.93 30
# macro avg 0.93 0.93 0.93 30
# weighted avg 0.93 0.93 0.93 30
print(accuracy_score(Y_test, Y_prediction))
# 0.9333333333333333
# predict sample
Y_prediction = classifier.predict(sample)
table = list(zip([list(np.round(x, 1)) for x in sample], Y_prediction))
print(tabulate(table, headers=['sample', 'label'], tablefmt="simple"))
# sample label
# -------------------- -------
# [4.4, 4.2, 1.0, 1.0] 0
# [7.9, 2.0, 3.7, 1.2] 1
# [4.0, 3.0, 4.3, 0.8] 1
# [5.7, 3.2, 3.0, 0.5] 1
# [6.2, 2.8, 2.3, 0.2] 0
# [5.3, 2.5, 1.7, 2.2] 0
# [4.9, 2.2, 7.0, 0.0] 2
# https://en.wikipedia.org/wiki/Artificial_neuron
import numpy as np
from tabulate import tabulate
# https://en.wikipedia.org/wiki/Heaviside_step_function
def H(x, w, threshold=1):
wx = np.dot(w, x)
if (wx >= threshold): return 1
else: return 0
assert (H([0.1, -0.5, 0.4], [0.1, -0.5, 0.4], 0) == 1)
assert (H([0.1, 0.5, 0.4], [0.1, -0.5, 0.4], 0) == 0)
table = []
# logical AND
threshold = 1.5
table.append(['AND', [0, 0], [1, 1], threshold, H([0, 0], [1, 1], threshold)])
table.append(['AND', [0, 1], [1, 1], threshold, H([0, 1], [1, 1], threshold)])
table.append(['AND', [1, 0], [1, 1], threshold, H([1, 0], [1, 1], threshold)])
table.append(['AND', [1, 1], [1, 1], threshold, H([1, 1], [1, 1], threshold)])
# logical NOT
threshold = -0.5
table.append(['NOT', [0], [-1], threshold, H([0], [-1], threshold)])
table.append(['NOT', [1], [-1], threshold, H([1], [-1], threshold)])
# logical OR
threshold = 0.5
table.append(['OR', [0, 0], [1, 1], threshold, H([0, 0], [1, 1], threshold)])
table.append(['OR', [0, 1], [1, 1], threshold, H([0, 1], [1, 1], threshold)])
table.append(['OR', [1, 0], [1, 1], threshold, H([1, 0], [1, 1], threshold)])
table.append(['OR', [1, 1], [1, 1], threshold, H([1, 1], [1, 1], threshold)])
# combination: (A AND NOT B) OR (A AND C) OR (NOT B AND C)
threshold = 1
table.append(['COMBINATION', [0, 0, 0], [2, -2, 2], threshold, H([0, 0, 0], [2, -2, 2], threshold)])
table.append(['COMBINATION', [1, 0, 0], [2, -2, 2], threshold, H([1, 0, 0], [2, -2, 2], threshold)])
table.append(['COMBINATION', [0, 1, 0], [2, -2, 2], threshold, H([0, 1, 0], [2, -2, 2], threshold)])
print(tabulate(table, headers=['unit', 'x', 'w', 'threshold', 'output'], tablefmt="simple"))
# unit x w threshold output
# ----------- --------- ---------- ----------- --------
# AND [0, 0] [1, 1] 1.5 0
# AND [0, 1] [1, 1] 1.5 0
# AND [1, 0] [1, 1] 1.5 0
# AND [1, 1] [1, 1] 1.5 1
# NOT [0] [-1] -0.5 1
# NOT [1] [-1] -0.5 0
# OR [0, 0] [1, 1] 0.5 0
# OR [0, 1] [1, 1] 0.5 1
# OR [1, 0] [1, 1] 0.5 1
# OR [1, 1] [1, 1] 0.5 1
# COMBINATION [0, 0, 0] [2, -2, 2] 1 0
# COMBINATION [1, 0, 0] [2, -2, 2] 1 1
# COMBINATION [0, 1, 0] [2, -2, 2] 1 0
"""
A simple implementation of linear layer followed by a
ReLU activation function.
"""
import numpy as np
dtype = "float32"
# numpy
a_np = np.random.rand(128, 128).astype(dtype)
b_np = np.random.rand(128, 128).astype(dtype)
# matmul -> relu
c_mm_relu = np.maximum(a_np @ b_np, 0)
# implementation
def mm_relu(A: np.ndarray, B: np.ndarray, C: np.ndarray):
# A, B, C: 128x128
Y = np.empty((128, 128), dtype=dtype)
# matmul
for i in range(128):
for j in range(128):
for k in range(128):
if k == 0: Y[i, j] = 0
Y[i, j] += A[i, k] * B[k, j]
# relu
for i in range(128):
for j in range(128): C[i, j] = max(Y[i, j], 0)
# test
c_np = np.empty((128, 128), dtype=dtype)
mm_relu(a_np, b_np, c_np)
# check within tolerance
np.testing.assert_allclose(c_mm_relu, c_np, rtol=1e-5)
# https://www.cs.princeton.edu/courses/archive/spring13/cos511/scribe_notes/0411.pdf
import numpy as np
from tabulate import tabulate
# initial values
w = [1, 0, 0]
# margin vector
v = [1, 1, 1, 1, 1, 1]
# learning rate
n = 0.1
# iterations
iterations = 12
# dataset
X = [[0, 2], [1, 2], [2, 1], [-3, 1], [-2, 1], [-3, 2]]
Y = [[1, 0, 2], [1, 1, 2], [1, 2, 1], [-1, 3, -1], [-1, 2, 1], [-1, 3, 2]]
# sequential widrow-hoff learning algorithm
result = []
for o in range(int(iterations / len(Y))):
for i in range(len(Y)):
w_prev = w
y = Y[i]
# calculate wy
wy = np.dot(w, y)
# calculate update part
update = np.zeros(len(y))
for j in range(len(y)): update[j] = n * (v[i] - wy) * y[j]
# add update part to a
w = np.add(w, update)
# append result
result.append([
# i
i + 1 + (len(Y) * o),
# w
[round(x, 3) for x in w_prev],
# y
list(y),
# wy
round(wy, 3),
# w_new
[round(x, 3) for x in w]
])
print(tabulate(result, headers=['i', 'w', 'y', 'wy', 'w_new'], tablefmt="simple"))
# i w y wy w_new
# --- ---------------------- ----------- ------ ----------------------
# 1 [1, 0, 0] [1, 0, 2] 1 [1.0, 0.0, 0.0]
# 2 [1.0, 0.0, 0.0] [1, 1, 2] 1 [1.0, 0.0, 0.0]
# 3 [1.0, 0.0, 0.0] [1, 2, 1] 1 [1.0, 0.0, 0.0]
# 4 [1.0, 0.0, 0.0] [-1, 3, -1] -1 [0.8, 0.6, -0.2]
# 5 [0.8, 0.6, -0.2] [-1, 2, 1] 0.2 [0.72, 0.76, -0.12]
# 6 [0.72, 0.76, -0.12] [-1, 3, 2] 1.32 [0.752, 0.664, -0.184]
# 7 [0.752, 0.664, -0.184] [1, 0, 2] 0.384 [0.814, 0.664, -0.061]
# 8 [0.814, 0.664, -0.061] [1, 1, 2] 1.356 [0.778, 0.628, -0.132]
# 9 [0.778, 0.628, -0.132] [1, 2, 1] 1.903 [0.688, 0.448, -0.222]
# 10 [0.688, 0.448, -0.222] [-1, 3, -1] 0.878 [0.676, 0.484, -0.234]
# 11 [0.676, 0.484, -0.234] [-1, 2, 1] 0.059 [0.581, 0.673, -0.14]
# 12 [0.581, 0.673, -0.14] [-1, 3, 2] 1.156 [0.597, 0.626, -0.172]
#1-multiples-of-3-and-5.py#2-even-fibonacci-numbers.py#3-largest-prime-factor.py#4-largest-palindrome-product.py#5-smallest-multiple.py#6-sum-square-difference.py#7-10001st-prime.py#8-largest-product-in-a-series.py#9-special-pythagorean-triplet.py#10-summation-of-primes.py#11-largest-product-in-grid.py#12-highly-divisible-triangular-number.py#13-large-sum.py#14-longest-collatz-sequence.py#15-lattice-paths.py#16-power-digit-sum.py#17-number-letter-counts.py
"""
Multiples of 3 and 5
If we list all the natural numbers below 10 that are multiples
of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is
23.
Find the sum of all the multiples of 3 or 5 below 1000.
https://projecteuler.net/problem=1
"""
# solution
result = list()
for n in list(range(1000))[1:]:
if n % 3 == 0 or n % 5 == 0: result.append(n)
print(sum(result)) # 233168
# 2020-10
"""
Even Fibonacci numbers
Each new term in the Fibonacci sequence is generated by
adding the previous two terms. By starting with 1 and 2,
the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34,
55, 89, ...
By considering the terms in the Fibonacci sequence whose
values do not exceed four million, find the sum of the
even-valued terms.
https://projecteuler.net/problem=2
"""
# test
# seq = list()
# for n in list(range(10)):
# if n == 0:
# seq.append(1)
# if n == 1:
# seq.append(2)
# if n > 1:
# seq.append(seq[n - 2] + seq[n - 1])
# assert(seq == list([1, 2, 3, 5, 8, 13, 21, 34, 55, 89]))
# solution
seq = list()
result = list()
max_value = 4000000
n = 0
while True:
if n == 0:
seq.append(1)
if n == 1:
seq.append(2)
if n > 1:
seq.append(seq[n - 2] + seq[n - 1])
# break condition
if seq[n] > max_value:
seq.pop(n)
break
# even
if seq[n] % 2 == 0:
result.append(seq[n])
n += 1
print(sum(result))
# 4613732
# 2020-10
"""
Largest prime factor
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143?
https://projecteuler.net/problem=3
"""
# test
# number = 13195
# result = list()
# factor = number - 1
# while factor > 1:
# if number % factor == 0:
# # factor
# subfactor = factor - 1
# while subfactor > 1:
# if factor % subfactor == 0:
# break
# subfactor -= 1
# if subfactor == 1:
# result.append(factor)
# factor -= 1
# assert(max(result) == 29)
# solution (too slow)
# number = 600851475143
# result = list()
# factor = number - 1
# while factor > 1:
# if number % factor == 0:
# # factor
# subfactor = factor - 1
# while subfactor > 1:
# if factor % subfactor == 0:
# break
# subfactor -= 1
# if subfactor == 1:
# print(factor)
# result.append(factor)
# factor -= 1
# print(max(result))
# solution (faster)
import math
number = 600851475143
result = list()
while number % 2 == 0:
result.append(2)
number = number / 2
for i in range(3, int(math.sqrt(number)) + 1, 2):
while number % i == 0:
result.append(i)
number = number / i
if number > 2:
result.append(number)
print(max(result))
# 6857
# 2020-10
"""
Largest palindrome product
A palindromic number reads the same both ways. The
largest palindrome made from the product of two 2-digit
numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.
https://projecteuler.net/problem=4
"""
# test
# MAX_2 = 100
# nlst = list(range(MAX_2))[80:]
# result = list()
# for i in nlst:
# for j in nlst:
# product = i * j
# if list(str(product)) == list(str(product))[::-1]:
# result.append(product)
# assert(max(result) == 9009)
# solution
MAX_2 = 1000
nlst = list(range(MAX_2))[800:]
result = list()
for i in nlst:
for j in nlst:
product = i * j
if list(str(product)) == list(str(product))[::-1]:
result.append(product)
print(max(result))
# 906609
# 2020-10
"""
Smallest multiple
2520 is the smallest number that can be divided by
each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly
divisible by all of the numbers from 1 to 20?
https://projecteuler.net/problem=5
"""
# test
# MAX_ITER = 10000
# number = 1
# nlst = list(range(1, 11))
# result = -1
# while number < MAX_ITER:
# divisible = True
# for n in nlst:
# if number % n != 0:
# divisible = False
# break
# if divisible:
# result = number
# break
# number += 1
# assert(result == 2520)
# solution
MAX_ITER = 1000000000
number = 1
nlst = list(range(11, 21))
result = -1
while number < MAX_ITER:
divisible = True
for n in nlst:
if number % n != 0:
divisible = False
break
if divisible:
result = number
break
number += 1
print(result)
# 232792560
# 2020-11
"""
Sum square difference
The sum of the squares of the first ten natural numbers
is, 1^2 + 2^2 + ... + 10^2 = 385.
The square of the sum of the first ten natural numbers
is, (1 + 2 + ... + 10^2) = 55^2 = 3025.
Hence the difference between the sum of the squares of
the first ten natural numbers and the square of the sum
is 3025 - 385 = 2640.
Find the difference between the sum of the squares of the
first one hundred natural numbers and the square of the sum.
https://projecteuler.net/problem=6
"""
# test
# nlist = list(range(1, 11))
# sum_square = 0
# for n in nlist:
# sum_square += (n ** 2)
# square_sum = sum(nlist) ** 2
# assert(square_sum - sum_square == 2640)
# solution
nlist = list(range(1, 101))
sum_square = 0
for n in nlist:
sum_square += (n ** 2)
square_sum = sum(nlist) ** 2
print(square_sum - sum_square)
# 25164150
# 2020-10
"""
10001st prime
By listing the first six prime numbers: 2, 3, 5, 7,
11, and 13, we can see that the 6th prime is 13.
What is the 10001st prime number?
# https://projecteuler.net/problem=7
"""
import numpy as np
# test (too slow)
# algorithm:
# π(n) = (sum from j=2 to n) [ ((j-1)! + 1)/j - [(j-1)!/j] ]
# nth prime = 1 + (sum from m=1 to j=2 ** n) [ [ n/(1 + π(m)) ]1/n ]
# [x] is floor function
# def pi(n):
# pi_n = 0
# for j in range(n + 1):
# if j < 2:
# pass
# else:
# pi_n += math.floor(((math.factorial(j - 1) + 1) // j) - math.floor(math.factorial(j - 1) // j))
# return pi_n
# def n_prime(n):
# n_prime = 0
# for m in range(2 ** n + 1):
# if m < 1:
# pass
# else:
# n_prime += math.floor(math.floor(n // (1 + pi(m))) ** (1 / n))
# n_prime += 1
# return n_prime
# assert(n_prime(6) == 13)
# solution
MAX_SIZE = 1000000
# sieve of eratosthenes
def SOE(primelst):
is_prime = np.ones(MAX_SIZE)
prime = 2
while (prime * prime) < MAX_SIZE:
if is_prime[prime] == True:
i = (prime * prime)
while i < MAX_SIZE:
is_prime[i] = 0
i += prime
prime += 1
prime = 2
while prime < MAX_SIZE:
if is_prime[prime]:
primelst.append(prime)
prime += 1
return primelst
result = SOE([])
n = 10001
print(result[n - 1])
# 104743
# 2020-11
"""
Largest product in a series
The four adjacent digits in the 1000-digit number that
have the greatest product are 9 × 9 × 8 × 9 = 5832.
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
Find the thirteen adjacent digits in the 1000-digit
number that have the greatest product. What is the
value of this product?
https://projecteuler.net/problem=8
"""
import numpy as np
str = '''
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
'''
nlist = list(''.join(str.strip().split('\n')))
nlist = list(map(int, nlist))
# test
# adj_digits = 4
# max_product = 0
# for i in range(len(nlist)):
# if (i + adj_digits > len(nlist)):
# break
# product = np.prod(nlist[i:i+adj_digits])
# if product > max_product:
# max_product = product
# assert(max_product == 5832)
# solution
adj_digits = 13
max_product = 0
for i in range(len(nlist)):
if (i + adj_digits > len(nlist)):
break
product = np.prod(nlist[i:i+adj_digits])
if product > max_product:
max_product = product
print(max_product)
# 23514624000
# 2020-11
"""
Special Pythagorean triplet
A Pythagorean triplet is a set of three
natural numbers, a < b < c, for which,
a^2 + b^2 = c^2.
For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2.
There exists exactly one Pythagorean triplet
for which a + b + c = 1000. Find the product
abc.
https://projecteuler.net/problem=9
"""
import numpy as np
# it is not pretty, but it works
MAX_N = 500
def brute(MAX_N):
for a in range(MAX_N):
for b in range(MAX_N):
for c in range(MAX_N):
if (a < b and b < c) and (a ** 2 + b ** 2 == c ** 2) and (a + b + c == 1000):
return (a, b, c), a * b * c
return 0
triplet, result = brute(MAX_N)
print(triplet)
# (200, 375, 425)
print(result)
# 31875000
"""
Summation of primes
The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.
https://projecteuler.net/problem=10
"""
import numpy as np
# sieve of eratosthenes
def SOE(primelst, MAX_SIZE=10):
is_prime = np.ones(MAX_SIZE)
prime = 2
while (prime * prime) < MAX_SIZE:
if is_prime[prime] == True:
i = (prime * prime)
while i < MAX_SIZE:
is_prime[i] = 0
i += prime
prime += 1
prime = 2
while prime < MAX_SIZE:
if is_prime[prime]: primelst.append(prime)
prime += 1
return primelst
assert(sum(SOE([], 10)) == 17)
result = SOE([], 2000000)
print(sum(result)) # 142913828922
"""
Largest product in grid
In the 20x20 grid below, four numbers along a diagonal line
have been marked in red.
The product of these numbers is 26 * 63 * 78 * 14 = 1788696.
What is the greatest product of four adjacent numbers in the
same direction (up, down, left, right, or diagonally) in the
20x20 grid?
https://projecteuler.net/problem=11
"""
import numpy as np
# solution
GRID = [
['08', '02', '22', '97', '38', '15', '00', '40', '00', '75', '04', '05', '07', '78', '52', '12', '50', '77', '91', '08'],
['49', '49', '99', '40', '17', '81', '18', '57', '60', '87', '17', '40', '98', '43', '69', '48', '04', '56', '62', '00'],
['81', '49', '31', '73', '55', '79', '14', '29', '93', '71', '40', '67', '53', '88', '30', '03', '49', '13', '36', '65'],
['52', '70', '95', '23', '04', '60', '11', '42', '69', '24', '68', '56', '01', '32', '56', '71', '37', '02', '36', '91'],
['22', '31', '16', '71', '51', '67', '63', '89', '41', '92', '36', '54', '22', '40', '40', '28', '66', '33', '13', '80'],
['24', '47', '32', '60', '99', '03', '45', '02', '44', '75', '33', '53', '78', '36', '84', '20', '35', '17', '12', '50'],
['32', '98', '81', '28', '64', '23', '67', '10', '26', '38', '40', '67', '59', '54', '70', '66', '18', '38', '64', '70'],
['67', '26', '20', '68', '02', '62', '12', '20', '95', '63', '94', '39', '63', '08', '40', '91', '66', '49', '94', '21'],
['24', '55', '58', '05', '66', '73', '99', '26', '97', '17', '78', '78', '96', '83', '14', '88', '34', '89', '63', '72'],
['21', '36', '23', '09', '75', '00', '76', '44', '20', '45', '35', '14', '00', '61', '33', '97', '34', '31', '33', '95'],
['78', '17', '53', '28', '22', '75', '31', '67', '15', '94', '03', '80', '04', '62', '16', '14', '09', '53', '56', '92'],
['16', '39', '05', '42', '96', '35', '31', '47', '55', '58', '88', '24', '00', '17', '54', '24', '36', '29', '85', '57'],
['86', '56', '00', '48', '35', '71', '89', '07', '05', '44', '44', '37', '44', '60', '21', '58', '51', '54', '17', '58'],
['19', '80', '81', '68', '05', '94', '47', '69', '28', '73', '92', '13', '86', '52', '17', '77', '04', '89', '55', '40'],
['04', '52', '08', '83', '97', '35', '99', '16', '07', '97', '57', '32', '16', '26', '26', '79', '33', '27', '98', '66'],
['88', '36', '68', '87', '57', '62', '20', '72', '03', '46', '33', '67', '46', '55', '12', '32', '63', '93', '53', '69'],
['04', '42', '16', '73', '38', '25', '39', '11', '24', '94', '72', '18', '08', '46', '29', '32', '40', '62', '76', '36'],
['20', '69', '36', '41', '72', '30', '23', '88', '34', '62', '99', '69', '82', '67', '59', '85', '74', '04', '36', '16'],
['20', '73', '35', '29', '78', '31', '90', '01', '74', '31', '49', '71', '48', '86', '81', '16', '23', '57', '05', '54'],
['01', '70', '54', '71', '83', '51', '54', '69', '16', '92', '33', '48', '61', '43', '52', '01', '89', '19', '67', '48']
]
GRID = np.array(GRID).astype(int)
WINDOW_SIZE = 4
# largest product
def largest_product(GRID):
max_product = 0
for i in range(GRID.shape[0] - (WINDOW_SIZE - 1)):
for j in range(GRID.shape[1] - (WINDOW_SIZE - 1)):
window = np.array(GRID[i:WINDOW_SIZE + i, j:WINDOW_SIZE + j])
windowT = window.T
# print(window)
# print(windowT)
products = []
# rows and columns
for n in range(window.shape[0]):
# rows
products.append(np.prod(window[n]))
# columns
products.append(np.prod(windowT[n]))
# diagonal
diagonal = []
for n in range(window.shape[0]):
diagonal.append(window[n][n])
products.append(np.prod(diagonal))
# diagonal: reversed
diagonal_reversed = []
for n in range(windowT.shape[0]):
diagonal_reversed.append(window[(WINDOW_SIZE - 1) - n][n])
products.append(np.prod(diagonal_reversed))
# window max product
window_max = max(products)
if window_max > max_product:
max_product = window_max
return max_product
result = largest_product(GRID)
print(result) # 70600674
"""
Highly divisible triangular number
The sequence of triangle numbers is generated by adding the natural numbers. So the
7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms
would be: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
Let us list the factors of the first seven triangle numbers:
1 : 1
3 : 1,3
6 : 1,2,3,6
10 : 1,2,5,10
15 : 1,3,5,15
21 : 1,3,7,21
28 : 1,2,4,7,14,28
We can see that 28 is the first triangle number to have over five divisors.
What is the value of the first triangle number to have over five hundred divisors?
https://projecteuler.net/problem=12
"""
def triangle_number(number): return sum(list(range(number + 1)))
# test (slow)
def factors(factor_lst, number):
# append known factors
factor_lst.append(number)
factor_lst.append(number / 2)
factor_lst.append(1)
# set first factor (no factor larger than number / 2)
factor = number / 2 - 1
while factor > 1:
if number % factor == 0: factor_lst.append(factor)
factor -= 1
return len(factor_lst)
assert triangle_number(7) == 28
assert factors([], 28) == 6
# solution
import math
def factors_fast(factor_lst, n):
factor = 1
while factor <= math.sqrt(n):
if n % factor == 0:
if n / factor == factor: factor_lst.append(factor)
else:
factor_lst.append(factor)
factor_lst.append(int(n / factor))
factor = factor + 1
return len(factor_lst)
assert factors_fast([], 28) == 6
MAX_RANGE = 15000
MIN_LEN = 500
result = 0
for n in range(MAX_RANGE):
tn = triangle_number(n)
f = factors_fast([], tn)
if f > MIN_LEN:
result = tn, f
break
print(result[0])
# 76576500
# 2022-07
"""
Large sum
Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.
https://projecteuler.net/problem=13
"""
numbers = """37107287533902102798797998220837590246510135740250
46376937677490009712648124896970078050417018260538
74324986199524741059474233309513058123726617309629
91942213363574161572522430563301811072406154908250
23067588207539346171171980310421047513778063246676
89261670696623633820136378418383684178734361726757
28112879812849979408065481931592621691275889832738
44274228917432520321923589422876796487670272189318
47451445736001306439091167216856844588711603153276
70386486105843025439939619828917593665686757934951
62176457141856560629502157223196586755079324193331
64906352462741904929101432445813822663347944758178
92575867718337217661963751590579239728245598838407
58203565325359399008402633568948830189458628227828
80181199384826282014278194139940567587151170094390
35398664372827112653829987240784473053190104293586
86515506006295864861532075273371959191420517255829
71693888707715466499115593487603532921714970056938
54370070576826684624621495650076471787294438377604
53282654108756828443191190634694037855217779295145
36123272525000296071075082563815656710885258350721
45876576172410976447339110607218265236877223636045
17423706905851860660448207621209813287860733969412
81142660418086830619328460811191061556940512689692
51934325451728388641918047049293215058642563049483
62467221648435076201727918039944693004732956340691
15732444386908125794514089057706229429197107928209
55037687525678773091862540744969844508330393682126
18336384825330154686196124348767681297534375946515
80386287592878490201521685554828717201219257766954
78182833757993103614740356856449095527097864797581
16726320100436897842553539920931837441497806860984
48403098129077791799088218795327364475675590848030
87086987551392711854517078544161852424320693150332
59959406895756536782107074926966537676326235447210
69793950679652694742597709739166693763042633987085
41052684708299085211399427365734116182760315001271
65378607361501080857009149939512557028198746004375
35829035317434717326932123578154982629742552737307
94953759765105305946966067683156574377167401875275
88902802571733229619176668713819931811048770190271
25267680276078003013678680992525463401061632866526
36270218540497705585629946580636237993140746255962
24074486908231174977792365466257246923322810917141
91430288197103288597806669760892938638285025333403
34413065578016127815921815005561868836468420090470
23053081172816430487623791969842487255036638784583
11487696932154902810424020138335124462181441773470
63783299490636259666498587618221225225512486764533
67720186971698544312419572409913959008952310058822
95548255300263520781532296796249481641953868218774
76085327132285723110424803456124867697064507995236
37774242535411291684276865538926205024910326572967
23701913275725675285653248258265463092207058596522
29798860272258331913126375147341994889534765745501
18495701454879288984856827726077713721403798879715
38298203783031473527721580348144513491373226651381
34829543829199918180278916522431027392251122869539
40957953066405232632538044100059654939159879593635
29746152185502371307642255121183693803580388584903
41698116222072977186158236678424689157993532961922
62467957194401269043877107275048102390895523597457
23189706772547915061505504953922979530901129967519
86188088225875314529584099251203829009407770775672
11306739708304724483816533873502340845647058077308
82959174767140363198008187129011875491310547126581
97623331044818386269515456334926366572897563400500
42846280183517070527831839425882145521227251250327
55121603546981200581762165212827652751691296897789
32238195734329339946437501907836945765883352399886
75506164965184775180738168837861091527357929701337
62177842752192623401942399639168044983993173312731
32924185707147349566916674687634660915035914677504
99518671430235219628894890102423325116913619626622
73267460800591547471830798392868535206946944540724
76841822524674417161514036427982273348055556214818
97142617910342598647204516893989422179826088076852
87783646182799346313767754307809363333018982642090
10848802521674670883215120185883543223812876952786
71329612474782464538636993009049310363619763878039
62184073572399794223406235393808339651327408011116
66627891981488087797941876876144230030984490851411
60661826293682836764744779239180335110989069790714
85786944089552990653640447425576083659976645795096
66024396409905389607120198219976047599490197230297
64913982680032973156037120041377903785566085089252
16730939319872750275468906903707539413042652315011
94809377245048795150954100921645863754710598436791
78639167021187492431995700641917969777599028300699
15368713711936614952811305876380278410754449733078
40789923115535562561142322423255033685442488917353
44889911501440648020369068063960672322193204149535
41503128880339536053299340368006977710650566631954
81234880673210146739058568557934581403627822703280
82616570773948327592232845941706525094512325230608
22918802058777319719839450180888072429661980811197
77158542502016545090413245809786882778948721859617
72107838435069186155435662884062257473692284509516
20849603980134001723930671666823555245252804609722
53503534226472524250874054075591789781264330331690"""
result = 0
for line in numbers.split('\n'):
result = result + int(line[0:12])
print(str(result)[0:10])
# 5537376230
# 2022-07
"""
Longest Collatz sequence
The following iterative sequence is defined for the set of positive integers:
n -> n / 2 (n is even)
n -> 3n + 1 (n is odd)
Using the rule above and starting with 13, we generate the following sequence:
13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
It can be seen that this sequence (starting at 13 and finishing at 1) contains
10 terms. Although it has not been proved yet (Collatz Problem), it is thought
that all starting numbers finish at 1.
Which starting number, under one million, produces the longest chain?
https://projecteuler.net/problem=14
"""
def collatz(seq_lst, n):
# append starting value
seq_lst.append(int(n))
while n > 1:
# even
if n % 2 == 0:
n = n / 2
seq_lst.append(int(n))
# odd
else:
n = 3 * n + 1
seq_lst.append(int(n))
return seq_lst
assert collatz([], 13) == [13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
# solution (slow)
MAX_RANGE = 1000000
longest = (0, 0)
for n in range(MAX_RANGE):
seq = collatz([], n)
if len(seq) > longest[1]:
longest = (n, len(seq))
print(longest[0])
# 837799
# 2022-07
"""
Lattice paths
Starting in the top left corner of a 2×2 grid, and only being able to
move to the right and down, there are exactly 6 routes to the bottom
right corner.
How many such routes are there through a 20×20 grid?
https://projecteuler.net/problem=15
"""
import numpy as np
"""
pascal triangle (2x2 -> 3x3 grid line): 6 paths
1 1 1
1 2 3
1 3 6
pascal triangle (3x3 -> 4x4 grid line) : 20 paths
1 1 1 1
1 2 3 4
1 3 6 10
1 4 10 20
"""
# https://en.wikipedia.org/wiki/Pascal%27s_triangle
def pascal_triangle(size):
grid = np.ones((size, size))
for i in range(size):
if i > 0:
for j in range(size):
if j > 0:
grid[i][j] = grid[i - 1][j] + grid[i][j - 1]
return grid
assert int(pascal_triangle(3)[2][2]) == 6
assert int(pascal_triangle(4)[3][3]) == 20
print(int(pascal_triangle(21)[20][20]))
# 137846528820
# 2022-07
"""
Power digit sum
2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
What is the sum of the digits of the number 2^1000?
https://projecteuler.net/problem=16
"""
def pow_sum(n, p):
return sum(list(map(int, list(str(n ** p)))))
assert pow_sum(2, 15) == 26
print(pow_sum(2, 1000))
# 1366
# 2022-07
"""
Number letter counts
If the numbers 1 to 5 are written out in words: one, two, three,
four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in
total.
If all the numbers from 1 to 1000 (one thousand) inclusive were
written out in words, how many letters would be used?
https://projecteuler.net/problem=17
"""
words = {
1: 'one',
2: 'two',
3: 'three',
4: 'four',
5: 'five',
6: 'six',
7: 'seven',
8: 'eight',
9: 'nine',
10: 'ten',
11: 'eleven',
12: 'twelve',
13: 'thirteen',
14: 'fourteen',
15: 'fifteen',
16: 'sixteen',
17: 'seventeen',
18: 'eighteen',
19: 'nineteen',
20: 'twenty',
30: 'thirty',
40: 'forty',
50: 'fifty',
60: 'sixty',
70: 'seventy',
80: 'eighty',
90: 'ninety',
100: 'hundred',
1000: 'thousand'
}
def parse_number(word_lst, n):
number = str(n)
size = len(number) - 1
for i in range(len(number)):
digit = number[i]
# convert to teens
if size == 1 and int(digit + number[i + 1]) in words:
if i > 0: word_lst.append('and')
word_lst.append(words[int(digit + number[i + 1])])
break
# convert to tens
elif size == 1 and int(digit + '0') in words:
if i > 0: word_lst.append('and')
word_lst.append(words[int(digit + '0')])
else:
if int(digit) > 0:
word_lst.append(words[int(digit)])
# thousands
if size == 3:
word_lst.append(words[1000])
break
# hundreds
if size == 2:
word_lst.append(words[100])
size -= 1
return word_lst
assert parse_number([], 342) == ['three', 'hundred', 'and', 'forty', 'two']
assert parse_number([], 115) == ['one', 'hundred', 'and', 'fifteen']
assert sum(list(map(len, parse_number([], 342)))) == 23
assert sum(list(map(len, parse_number([], 115)))) == 20
# numbers = []
letters = 0
n = 1
while n < len(range(1000)) + 1:
# number = parse_number([], n)
# numbers.append(number)
letters += sum(list(map(len, parse_number([], n))))
n += 1
print(letters)
# 21124
ast-constant-folding.pyast-to-tac-to-llvm.pydsl-in-python.pyfor-loop-implementation.pyloop-tiling-optimization.pyopencl-in-python.pyoperator-fusion-on-parse-tree.pyparallelization-optimization.pyshunting-yard-algorithm.pytokenizer-using-generator-in-python.pyvectorization-optimization.py
"""
Constant folding is a form of partial evaluation
that can be applied to constant expressions to
reduce the number of instructions in generated
code.
"""
import ast
program = """
x = 5
y = 10
z = x + y * 2
print(z)
"""
variables = {}
tree = ast.parse(program)
# print(len(ast.dump(tree)))
# 449
folded_tree = ast.Module(body=[], type_ignores=[])
# walk ast
for node in ast.walk(tree):
if isinstance(node, ast.Assign):
if isinstance(node.targets[0], ast.Name):
if isinstance(node.value, ast.Num):
variables[node.targets[0].id] = node.value.n
else:
folded_tree.body.append(node)
if isinstance(node, ast.BinOp):
if isinstance(node.left, ast.Name) and node.left.id in variables:
node.left = ast.Num(n=variables[node.left.id])
elif isinstance(node.right, ast.Name) and node.right.id in variables:
node.right = ast.Num(n=variables[node.right.id])
else:
folded_tree.body.append(node)
if isinstance(node, ast.Expr):
folded_tree.body.append(node)
# print(variables)
# print(ast.dump(folded_tree))
# print(len(ast.dump(folded_tree)))
# 295
# fix missing locations
ast.fix_missing_locations(folded_tree)
# compile and execute folded tree
exec(compile(folded_tree, filename="<ast>", mode="exec"))
# 25
"""
AST is tree representation of source code
TAC is linear representation of ASTs
LLVM IR is linear representation of the TAC
"""
from mako.template import Template
def gen_tac(ast, tmp_counter):
if isinstance(ast, int):
return f"t{tmp_counter} = {ast}", f"t{tmp_counter}", tmp_counter + 1
elif isinstance(ast, list):
op = ast[0]
left, left_var, tmp_counter = gen_tac(ast[1], tmp_counter)
right, right_var, tmp_counter = gen_tac(ast[2], tmp_counter)
tmp_var = f"t{tmp_counter}"
result = f"{tmp_var} = {left_var} {op} {right_var}"
return f"{left}\n{right}\n{result}", tmp_var, tmp_counter + 1
else:
raise Exception("unknown node")
def tac_to_llvm(tac):
code = []
var_map = {}
code.append("define i32 @main(i32) {")
for line in tac.strip().split('\n'):
parts = line.split(' ')
destination_var = parts[0]
operation = parts[1]
operands = parts[2:]
if len(parts) == 3 and operation == '=':
if operands and operands[0].isdigit():
code.append(f"\t%{destination_var} = add i32 {operands[0]}, 0")
else:
code.append(f"\t%{destination_var} = add i32 %{var_map[operands[0]]}, 0")
var_map[destination_var] = destination_var
else:
# replace assignment with operation
operation = parts[3]
if operands[0].isdigit():
op1 = f"{operands[0]}"
else:
op1 = f"%{var_map[operands[0]]}"
if operands[2].isdigit():
op2 = f"{operands[2]}"
else:
op2 = f"%{var_map[operands[2]]}"
if operation == '+':
code.append(f"\t%{destination_var} = add i32 {op1}, {op2}")
elif operation == '-':
code.append(f"\t%{destination_var} = sub i32 {op1}, {op2}")
elif operation == '*':
code.append(f"\t%{destination_var} = mul i32 {op1}, {op2}")
elif operation == '/':
code.append(f"\t%{destination_var} = sdiv i32 {op1}, {op2}")
else:
raise ValueError(f"Unsupported operation: {operation}")
var_map[destination_var] = destination_var
code.append(f"\tret i32 %{var_map[destination_var]}")
code.append("}")
return '\n'.join(code)
ast = ["+", 2, ["*", 3, 4]]
tac = gen_tac(ast, 1)[0]
# t1 = 2
# t2 = 3
# t3 = 4
# t4 = t2 * t3
# t5 = t1 + t4
print(tac_to_llvm(tac))
# define i32 @main(i32) {
# %t1 = add i32 2, 0
# %t2 = add i32 3, 0
# %t3 = add i32 4, 0
# %t4 = mul i32 %t2, %t3
# %t5 = add i32 %t1, %t4
# ret i32 %t5
# }
"""
This is how to design and use embedded
domain-specific languages in Python.
"""
import sys
"""
functions
add : sum all arguments
sub : subtract tail from head
types
int
float
arguments
out : stdin to use previous output as input
: stdout to print
"""
program = """
Module add 1 2 3 type=float out=stdin
Module sub stdin 1 2 type=int out=stdout
"""
# Module definition
class Module:
# Add function
def add(*args, **kwargs):
type_ = globals()["__builtins__"].getattr(globals()["__builtins__"], kwargs["type"])
return sum(map(type_, args))
# Sub function
def sub(*args, **kwargs):
type_ = globals()["__builtins__"].getattr(globals()["__builtins__"], kwargs["type"])
return float(args[0]) if type_ == 'float' else int(args[0]) - sum(map(type_, args[1:]))
def get_args(tokens, STDIN):
args = []
kwargs = {}
for token in tokens:
# kwargs
if '=' in token:
k, v = token.split('=', 1)
kwargs[k] = v
# args
else:
# replace stdin with previous output
if token == "stdin":
if STDIN != "": args.append(STDIN)
else: raise Exception("no previous output")
else:
args.append(token)
return args, kwargs
def interpret(program):
STDIN = ""
lines = [line for line in program.splitlines() if line]
# print(lines)
# ['Module add 1 2 3 type=float out=stdin', 'Module sub stdin 1 2 type=int out=stdout']
for line in lines:
tokens = line.split()
args, kwargs = get_args(tokens[2:], STDIN)
# print(args, kwargs)
# ['1', '2', '3'] {'type': 'float', 'out': 'stdin'}
# [6.0, '1', '2'] {'type': 'int', 'out': 'stdout'}
# print(getattr(sys.modules[__name__], tokens[0]))
# <class '__main__.Module'>
# <class '__main__.Module'>
# print(getattr(getattr(sys.modules[__name__], tokens[0]), tokens[1]))
# <function Module.add at 0x1024545e0>
# <function Module.sub at 0x108ed9620>
result = getattr(getattr(sys.modules[__name__], tokens[0]), tokens[1])(*args, **kwargs)
if "out" in kwargs:
if kwargs["out"] == "stdin": STDIN = result
if kwargs["out"] == "stdout": print(result)
interpret(program) # 3
import timeit
def not_for_loop(index = 0, elements = [], operation = None):
if index < len(elements):
if operation is not None:
elements[index] = operation(elements[index])
not_for_loop(index + 1, elements, operation)
return elements
def for_loop_using_while(elements = [], operation = None):
index = 0
while index < len(elements):
if operation is not None:
elements[index] = operation(elements[index])
index += 1
return elements
def for_loop(elements = [], operation = None):
for index in range(len(elements)):
elements[index] = operation(elements[index])
return elements
# print(not_for_loop(0, [1, 2, 3, 4, 5], lambda x: x.__add__(1)))
# print(for_loop_using_while([1, 2, 3, 4, 5], lambda x: x.__add__(1)))
# print(for_loop([1, 2, 3, 4, 5], lambda x: x.__add__(1)))
assert not_for_loop(0, [1, 2, 3, 4, 5], lambda x: x.__add__(1)) == [2, 3, 4, 5, 6]
assert for_loop_using_while([1, 2, 3, 4, 5], lambda x: x.__add__(1)) == [2, 3, 4, 5, 6]
assert for_loop([1, 2, 3, 4, 5], lambda x: x.__add__(1)) == [2, 3, 4, 5, 6]
print(timeit.timeit('not_for_loop(0, [1, 2, 3, 4, 5], lambda x: x.__add__(1))', setup = 'from __main__ import not_for_loop', number = 100000))
# 0.10954952286556363
print(timeit.timeit('for_loop_using_while([1, 2, 3, 4, 5], lambda x: x.__add__(1))', setup = 'from __main__ import for_loop_using_while', number = 100000))
# 0.08992556994780898
print(timeit.timeit('for_loop([1, 2, 3, 4, 5], lambda x: x.__add__(1))', setup = 'from __main__ import for_loop', number = 100000))
# 0.08654258819296956
"""
Loop tiling optimization is a technique used
to improve cache efficiency in nested loops.
"""
import random
import timeit
# timeit.template = """
# def inner(_it, _timer{init}):
# from tqdm import tqdm
# {setup}
# _t0 = _timer()
# for _i in tqdm(_it, total=_it.__length_hint__()):
# {stmt}
# _t1 = _timer()
# return _t1 - _t0
# """
# matrix multiplication
def matmul(A, B):
m, n, p = len(A), len(A[0]), len(B[0])
result = [[0 for _ in range(p)] for _ in range(m)]
for i in range(m):
for j in range(p):
for k in range(n):
result[i][j] += A[i][k] * B[k][j]
return result
A = [[1, 2, 3],[4, 5, 6],[7, 8, 9]]
B = [[9, 8, 7],[6, 5, 4],[3, 2, 1]]
assert matmul(A, B) == [[30, 24, 18], [84, 69, 54], [138, 114, 90]]
# tiling
TILE_SIZE = 100
def matmul_tiled(A, B):
m, n, p = len(A), len(A[0]), len(B[0])
result = [[0 for _ in range(p)] for _ in range(m)]
for i in range(0, m, TILE_SIZE):
for j in range(0, p, TILE_SIZE):
for k in range(0, n, TILE_SIZE):
for ii in range(i, min(i + TILE_SIZE, m)):
for jj in range(j, min(j + TILE_SIZE, p)):
for kk in range(k, min(k + TILE_SIZE, n)):
result[ii][jj] += A[ii][kk] * B[kk][jj]
return result
assert matmul_tiled(A, B) == [[30, 24, 18], [84, 69, 54], [138, 114, 90]]
A = [[random.random() for _ in range(200)] for _ in range(200)]
B = [[random.random() for _ in range(200)] for _ in range(200)]
print(timeit.timeit(lambda: matmul(A, B), number=10))
# 6.854414212051779
print(timeit.timeit(lambda: matmul_tiled(A, B), number=10)) # CPU
# 6.588905839016661
"""
OpenCL can be used to run code on GPUs and other
accelerators. It's a C API (kernel code looks like
C code) and pyopencl is a Python wrapper.
"""
import pyopencl as cl
import numpy as np
import timeit
# init opencl
platform = cl.get_platforms()[0]
device = platform.get_devices()[2] # AMD Radeon Pro 5500M Compute Engine
context = cl.Context([device])
queue = cl.CommandQueue(context)
# print(platform.get_info(cl.platform_info.NAME))
print(platform.get_info(cl.platform_info.VERSION))
# OpenCL 1.2 (Mar 4 2023 12:44:39)
print(device.get_info(cl.device_info.NAME))
# AMD Radeon Pro 5500M Compute Engine
# init data
size = 1000000000
# create arrays
a = np.random.rand(size).astype(np.float32)
b = np.random.rand(size).astype(np.float32)
result = np.zeros(size).astype(np.float32)
# opencl kernel
kernel_code = """
__kernel void add(__global float *a, __global float *b, __global float *result, int size) {
int idx = get_global_id(0);
if (idx < size) {
result[idx] = a[idx] + b[idx];
}
}
"""
# compile kernel
program = cl.Program(context, kernel_code).build()
# create buffers
a_buffer = cl.Buffer(context, cl.mem_flags.READ_ONLY | cl.mem_flags.COPY_HOST_PTR, hostbuf=a)
b_buffer = cl.Buffer(context, cl.mem_flags.READ_ONLY | cl.mem_flags.COPY_HOST_PTR, hostbuf=b)
result_buffer = cl.Buffer(context, cl.mem_flags.WRITE_ONLY, result.nbytes)
# opencl result
def run_opencl():
# execute kernel
program.add(queue, a.shape, None, a_buffer, b_buffer, result_buffer, np.int32(size))
# copy result
cl.enqueue_copy(queue, result, result_buffer)
# numpy result to compare with
numpy_result = np.zeros(size).astype(np.float32)
def run_numpy():
global numpy_result
numpy_result = a + b
print(timeit.timeit('run_numpy', globals=globals(), number=1))
# 1.0561197996139526e-06
print(timeit.timeit('run_opencl', globals=globals(), number=1))
# 5.420297384262085e-07
assert np.allclose(result, numpy_result)
# free memory
a_buffer.release()
b_buffer.release()
result_buffer.release()
# close opencl
del context
del queue
del program
"""
Operator fusion is a technique to combine or rearrange
consecutive operations in a parse tree to improve
efficiency of code execution.
"""
def simplify_parse_tree(tree):
if (isinstance(tree, tuple)):
# first value in tuple, remaining values in tuple
operator, *operands = tree
operands = [simplify_parse_tree(operand) for operand in operands]
if all(isinstance(operand, int) for operand in operands):
if operator == '+':
return sum(operands)
elif operator == '*':
return eval('*'.join(map(str, operands)))
return tree
# (1 + 2) * (3 + 4)
parse_tree = ('*', ('+', 1, 2), ('+', 3, 4))
print(simplify_parse_tree(parse_tree)) # 21
compiled = compile('(1 + 2) * (3 + 4)', '<string>', 'eval')
print(compiled.co_consts[0]) # 21
assert simplify_parse_tree(parse_tree) == compiled.co_consts[0]
"""
Parallelization optimization is a form of optimization
that aims to improve program performance by parallelizing
it, i.e. by splitting the program into smaller parts that
can be executed at the same time.
"""
import multiprocessing as mp
import timeit
# timeit.template = """
# def inner(_it, _timer{init}):
# from tqdm import tqdm
# {setup}
# _t0 = _timer()
# for _i in tqdm(_it, total=_it.__length_hint__()):
# {stmt}
# _t1 = _timer()
# return _t1 - _t0
# """
def sum_of_squares(numbers):
return sum([num * num for num in numbers])
def sum_of_squares_parallel(numbers):
# use all available cores
num_processes = mp.cpu_count()
chunk_size = len(numbers) // num_processes
# create pool of processes
pool = mp.Pool(processes=num_processes)
# divide work into chunks
chunks = [numbers[i:i + chunk_size] for i in range(0, len(numbers), chunk_size)]
results = pool.map(sum_of_squares, chunks)
# close
pool.close()
# combine results
pool.join()
return sum(results)
if __name__ == '__main__':
assert sum_of_squares(list(range(1, 10000))) == sum_of_squares_parallel(list(range(1, 10000)))
# timeit
n = list(range(1, 10000000))
print(f"sum_of_squares: {timeit.timeit(lambda: sum_of_squares(n), number=10)}")
# sum_of_squares: 7.48474136996083
print(f"sum_of_squares_parallel: {timeit.timeit(lambda: sum_of_squares_parallel(n), number=10)}")
# sum_of_squares_parallel: 6.641842097043991
# https://en.wikipedia.org/wiki/Shunting-yard_algorithm
PRECEDENCE = { 'func': 3, '^': 2, '/': 1, '*': 1, '+': 0, '-': 0 }
def parse(input_):
operator = []
output = []
tokens = list(input_)
while len(tokens) > 0:
char = tokens[0]
# number
if char.isnumeric(): output.append(char)
# function
if char.isalpha():
function = [char]
i = 1
while tokens[i].isalpha():
function.append(tokens[i])
i += 1
operator.append(('func', ''.join(function)))
# advance
tokens = tokens[i - 1:]
# operator
if char in ['+', '-', '*', '/', '^']:
# precedence
while len(operator) > 0:
op = operator.pop()
if op[0] == 'func':
output.append(op[1])
elif op not in ['(', '^'] and (op in PRECEDENCE and PRECEDENCE[op] >= PRECEDENCE[char]):
output.append(op)
else:
# break
operator.append(op)
break
operator.append(char)
# left parenthesis
if char == '(': operator.append(char)
# right parenthesis
if char == ')':
if '(' not in operator: print("Error: Mismatched parentheses")
while len(operator) > 0:
op = operator.pop()
if op[0] == 'func': output.append(op[1])
elif op != '(': output.append(op)
else: break
tokens = tokens[1:]
# pop operators
while len(operator) > 0:
op = operator.pop()
if op[0] == 'func': output.append(op[1])
else: output.append(op)
return ' '.join(output)
assert parse("3 + 4 * 2 / (1 - 5) ^2 ^3") == "3 4 2 * 1 5 - 2 3 ^ ^ / +"
assert parse("sin(max(2, 3) / 3 * pi)") == "2 3 max 3 / pi * sin"
import re
token_pattern = r'[a-zA-Z_][a-zA-Z0-9_]*|\d+|<=|>=|==|!=|[<>]=?|=|[+\-*/;(){}]'
tokens = {
'if': 'IF',
'else': 'ELSE',
'number': 'NUM',
'identifier': 'ID',
'assignment': 'ASSIGN',
'operator': 'OP',
'unknown': '?',
}
# tokenize
def tokenize(code):
for match in re.findall(token_pattern, code):
# yield to return generator (lazy evaluation)
if tokens.get(match): yield (tokens[match], match)
elif match.isdigit(): yield (tokens['number'], match)
elif match.isidentifier(): yield (tokens['identifier'], match)
elif match in '=': yield (tokens['assignment'], match)
elif match in '+-*/<>': yield (tokens['operator'], match)
elif match in '()/{/};': pass
else: yield (tokens['unknown'], match)
code = """if (x < 10) { x = x + 1; }"""
for token in tokenize(code): print(token)
# ('IF', 'if')
# ('ID', 'x')
# ('OP', '<')
# ('NUM', '10')
# ('ID', 'x')
# ('ASSIGN', '=')
# ('ID', 'x')
# ('OP', '+')
# ('NUM', '1')
"""
Vectorization optimization is a technique for optimizing
programs by transforming sequential operations into
parallel operations (vector operations).
"""
import numpy as np
import timeit
from dis import dis
def add_arrays(a, b):
result = []
for i in range(len(a)):
result.append(a[i] + b[i])
return result
# vectorized
def add_arrays_vectorized(a, b):
return np.array(a) + np.array(b)
a = [1, 2, 3, 4, 5, 6, 7, 8, 9]
b = [9, 8, 7, 6, 5, 4, 3, 2, 1]
assert np.array(add_arrays(a, b)).all() == add_arrays_vectorized(a, b).all()
# test data
a = np.random.randint(0, 10, size=1000000)
b = np.random.randint(0, 10, size=1000000)
print(timeit.timeit(lambda: add_arrays(a, b), number=10))
# 2.4067575628869236
print(timeit.timeit(lambda: add_arrays_vectorized(a, b), number=10))
# 0.07865401287563145
dis(add_arrays)
# 4 0 RESUME 0
# 5 2 BUILD_LIST 0
# 4 STORE_FAST 2 (result)
# 6 6 LOAD_GLOBAL 1 (NULL + range)
# 18 LOAD_GLOBAL 3 (NULL + len)
# 30 LOAD_FAST 0 (a)
# 32 PRECALL 1
# 36 CALL 1
# 46 PRECALL 1
# 50 CALL 1
# 60 GET_ITER
# >> 62 FOR_ITER 38 (to 140)
# 64 STORE_FAST 3 (i)
# 7 66 LOAD_FAST 2 (result)
# 68 LOAD_METHOD 2 (append)
# 90 LOAD_FAST 0 (a)
# 92 LOAD_FAST 3 (i)
# 94 BINARY_SUBSCR
# 104 LOAD_FAST 1 (b)
# 106 LOAD_FAST 3 (i)
# 108 BINARY_SUBSCR
# 118 BINARY_OP 0 (+)
# 122 PRECALL 1
# 126 CALL 1
# 136 POP_TOP
# 138 JUMP_BACKWARD 39 (to 62)
# 8 >> 140 LOAD_FAST 2 (result)
# 142 RETURN_VALUE
dis(add_arrays_vectorized)
# 11 0 RESUME 0
# 12 2 LOAD_GLOBAL 1 (NULL + np)
# 14 LOAD_ATTR 1 (array)
# 24 LOAD_FAST 0 (a)
# 26 PRECALL 1
# 30 CALL 1
# 40 LOAD_GLOBAL 1 (NULL + np)
# 52 LOAD_ATTR 1 (array)
# 62 LOAD_FAST 1 (b)
# 64 PRECALL 1
# 68 CALL 1
# 78 BINARY_OP 0 (+)
# 82 RETURN_VALUE
; x86-64 (intel syntax)
section .text
global _main
_main:
mov rax, 0x02000004 ; write (4)
mov rdi, 1 ; stdout
mov rsi, message ; address of output
mov rdx, 10 ; bytes : "hello x86" + /n = 10
syscall ; invoke write
mov rax, 0x02000001 ; exit (1)
xor rdi, rdi ; 0
syscall ; invoke to exit
section .data
message:
db "hello x86", 10 ; define byte : text, \n (10)
; $ nasm -f macho64 hello-x86.asm
; $ ld hello-x86.o -o _hello -lSystem -L/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/lib
; $ ./_hello
; hello x86
and16.vand.vdmux4way.vdmux8way.vdmux.vmux4way16.vmux8way16.vmux16.vmux.vnand.vnot16.vnot.vor8way.vor16.vor.vxor.v
/*
And16(a, b) : For i = 0..15 out[i] = And(a[i], b[i])
*/
// gate-level
module and16_gate (output [15:0] out, input [15:0] a, b);
// operations
and(out[0], a[0], b[0]);
and(out[1], a[1], b[1]);
and(out[2], a[2], b[2]);
and(out[3], a[3], b[3]);
and(out[4], a[4], b[4]);
and(out[5], a[5], b[5]);
and(out[6], a[6], b[6]);
and(out[7], a[7], b[7]);
and(out[8], a[8], b[8]);
and(out[9], a[9], b[9]);
and(out[10], a[10], b[10]);
and(out[11], a[11], b[11]);
and(out[12], a[12], b[12]);
and(out[13], a[13], b[13]);
and(out[14], a[14], b[14]);
and(out[15], a[15], b[15]);
endmodule
// behavioural-level
module and16_behavioural (output reg [15:0] out, input [15:0] a, b);
always @ (a or b) begin
out = a & b;
end
endmodule
// test
module test;
reg [15:0] a, b;
wire [15:0] out;
// and16_gate Instance0 (out, a, b);
and16_behavioural Instance0 (out, a, b);
// note: #(n) : delay by n timestep (check time scale with $printtimescale)
initial begin
a[7:0] = 8'b11111111; b[7:0] = 8'b11111111; // 1, 1, 1, 1, 1, 1, 1, 1
a[15:8] = 8'b00000000; b[15:8] = 8'b11111111; // 0, 0, 0, 0, 0, 0, 0, 0
end
initial begin
$printtimescale;
// Time scale of (test) is 1s / 1s
#(0) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[0], b[0], out[0]);
#(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[1], b[1], out[1]);
#(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[2], b[2], out[2]);
#(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[3], b[3], out[3]);
#(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[4], b[4], out[4]);
#(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[5], b[5], out[5]);
#(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[6], b[6], out[6]);
#(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[7], b[7], out[7]);
#(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[8], b[8], out[8]);
#(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[9], b[9], out[9]);
#(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[10], b[10], out[10]);
#(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[11], b[11], out[11]);
#(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[12], b[12], out[12]);
#(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[13], b[13], out[13]);
#(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[14], b[14], out[14]);
#(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[15], b[15], out[15]);
// 0 | a = 1 | b = 1 | out = 1
// 1 | a = 1 | b = 1 | out = 1
// 2 | a = 1 | b = 1 | out = 1
// 3 | a = 1 | b = 1 | out = 1
// 4 | a = 1 | b = 1 | out = 1
// 5 | a = 1 | b = 1 | out = 1
// 6 | a = 1 | b = 1 | out = 1
// 7 | a = 1 | b = 1 | out = 1
// 8 | a = 0 | b = 1 | out = 0
// 9 | a = 0 | b = 1 | out = 0
// 10 | a = 0 | b = 1 | out = 0
// 11 | a = 0 | b = 1 | out = 0
// 12 | a = 0 | b = 1 | out = 0
// 13 | a = 0 | b = 1 | out = 0
// 14 | a = 0 | b = 1 | out = 0
// 15 | a = 0 | b = 1 | out = 0
end
endmodule
/*
And(a, b) : If a = b = 1 then out = 1 else out = 0
*/
// gate-level
module and_gate (output out, input a, b);
// wire : internal pin
wire w;
// operations (note: limited to nand-gates)
nand(w, a, b);
nand(out, w, w);
endmodule
// test
module test;
reg a, b;
wire out;
and_gate Instance0 (out, a, b);
// note: #(n) : delay by n timestep (check time scale with $printtimescale)
initial begin
#(0) a = 0; b = 0; // 0
#(1) a = 0; b = 1; // 0
#(1) a = 1; b = 0; // 0
#(1) a = 1; b = 1; // 1
end
initial begin
$printtimescale;
// Time scale of (_nand_test) is 1s / 1s
$monitor ("%1d | a = %d | b = %d | out = %d", $time, a, b, out);
// 0 | a = 0 | b = 0 | out = 0
// 1 | a = 0 | b = 1 | out = 0
// 2 | a = 1 | b = 0 | out = 0
// 3 | a = 1 | b = 1 | out = 1
end
endmodule
/*
DMux4way(in, sel) :
If sel = 00 then { a = in, b = c = d = 0 } else if
sel = 01 then { b = in, a = c = d = 0 } else if
sel = 10 then { c = in, a = b = d = 0 } else if
sel = 11 then { d = in, a = b = c = 0 }
*/
// dmux.v
module dmux_gate (output a, b, input in, sel);
// wire : internal pin
wire w1;
wire w2;
wire notsel;
// operations
not(notsel, sel);
and(a, in, notsel);
and(b, in, sel);
endmodule
// gate-level
module dmux4way_gate (output a, b, c, d, input in, input [1:0] sel);
wire ao, bo;
dmux_gate Instance0 (ao, bo, in, sel[0]);
dmux_gate Instance1 (a, b, ao, sel[1]);
dmux_gate Instance2 (c, d, bo, sel[1]);
endmodule
// behavioural-level
module dmux4way_behavioural (output reg a, b, c, d, input in, input [1:0] sel);
always @ (in or sel) begin
a = 1'b0;
b = 1'b0;
c = 1'b0;
d = 1'b0;
// note: 2'b : 2-bit
if (sel == 2'b00) begin
a = in;
end
else if (sel == 2'b10) begin
b = in;
end
else if (sel == 2'b01) begin
c = in;
end
else begin
d = in;
end
end
endmodule
// test
module test;
reg [1:0] sel;
reg in;
wire a, b, c, d;
// dmux4way_gate Instance0 (a, b, c, d, in, sel);
dmux4way_behavioural Instance0 (a, b, c, d, in, sel);
// note: #(n) : delay by n timestep (check time scale with $printtimescale)
initial begin
#(0) in = 1; sel[0] = 0; sel[1] = 0; // { a = 1, b = c = d = 0 }
#(1) in = 1; sel[0] = 0; sel[1] = 1; // { b = 1, a = c = d = 0 }
#(1) in = 1; sel[0] = 1; sel[1] = 0; // { c = 1, a = b = d = 0 }
#(1) in = 1; sel[0] = 1; sel[1] = 1; // { d = 1, a = b = c = 0 }
end
initial begin
$printtimescale;
// Time scale of (test) is 1s / 1s
$monitor ("%1d | in = %d | sel = [%d, %d] | a = %d | b = %d | c = %d | d = %d", $time, in, sel[0], sel[1], a, b, c, d);
// 0 | in = 1 | sel = [0, 0] | a = 1 | b = 0 | c = 0 | d = 0
// 1 | in = 1 | sel = [0, 1] | a = 0 | b = 1 | c = 0 | d = 0
// 2 | in = 1 | sel = [1, 0] | a = 0 | b = 0 | c = 1 | d = 0
// 3 | in = 1 | sel = [1, 1] | a = 0 | b = 0 | c = 0 | d = 1
end
endmodule
/*
DMux8way(in, sel) :
If sel = 000 then { a = in, b = c = d = e = f = g = h = 0 } else if
sel = 001 then { b = in, a = c = d = e = f = g = h = 0 } else if
sel = 010 then { c = in, a = b = d = e = f = g = h = 0 } else if
sel = 011 then { d = in, a = b = c = e = f = g = h = 0 } else if
sel = 100 then { e = in, a = b = c = d = f = g = h = 0 } else if
sel = 101 then { f = in, a = b = c = d = e = g = h = 0 } else if
sel = 110 then { g = in, a = b = c = d = e = f = h = 0 } else if
sel = 111 then { h = in, a = b = c = d = e = f = g = 0 }
*/
// dmux.v
module dmux_gate (output a, b, input in, sel);
// wire : internal pin
wire w1;
wire w2;
wire notsel;
// operations
not(notsel, sel);
and(a, in, notsel);
and(b, in, sel);
endmodule
// gate-level
module dmux8way_gate (output a, b, c, d, e, f, g, h, input in, input [2:0] sel);
wire ao, bo, aoo, boo, coo, doo;
dmux_gate Instance0 (ao, bo, in, sel[0]);
dmux_gate Instance1 (aoo, boo, ao, sel[1]);
dmux_gate Instance2 (coo, doo, bo, sel[1]);
dmux_gate Instance3 (a, b, aoo, sel[2]);
dmux_gate Instance4 (c, d, boo, sel[2]);
dmux_gate Instance5 (e, f, coo, sel[2]);
dmux_gate Instance6 (g, h, doo, sel[2]);
endmodule
// behavioural-level
module dmux8way_behavioural (output reg a, b, c, d, e, f, g, h, input in, input [2:0] sel);
always @ (in or sel) begin
a = 1'b0;
b = 1'b0;
c = 1'b0;
d = 1'b0;
e = 1'b0;
f = 1'b0;
g = 1'b0;
h = 1'b0;
// note: 3'b : 3 bit
if (sel == 3'b000) begin
a = in;
end
else if (sel == 3'b100) begin
b = in;
end
else if (sel == 3'b010) begin
c = in;
end
else if (sel == 3'b110) begin
d = in;
end
else if (sel == 3'b001) begin
e = in;
end
else if (sel == 3'b101) begin
f = in;
end
else if (sel == 3'b011) begin
g = in;
end
else begin
h = in;
end
end
endmodule
// test
module test;
reg [2:0] sel;
reg in;
wire a, b, c, d, e, f, g, h;
// dmux8way_gate Instance0 (a, b, c, d, e, f, g, h, in, sel);
dmux8way_behavioural Instance0 (a, b, c, d, e, f, g, h, in, sel);
// note: #(n) : delay by n timestep (check time scale with $printtimescale)
initial begin
#(0) in = 1; sel[0] = 0; sel[1] = 0; sel[2] = 0; // { a = 1, b = c = d = e = f = g = h = 0 }
#(1) in = 1; sel[0] = 0; sel[1] = 0; sel[2] = 1; // { b = 1, a = c = d = e = f = g = h = 0 }
#(1) in = 1; sel[0] = 0; sel[1] = 1; sel[2] = 0; // { c = 1, a = b = d = e = f = g = h = 0 }
#(1) in = 1; sel[0] = 0; sel[1] = 1; sel[2] = 1; // { d = 1, a = b = c = e = f = g = h = 0 }
#(1) in = 1; sel[0] = 1; sel[1] = 0; sel[2] = 0; // { e = 1, a = b = c = d = f = g = h = 0 }
#(1) in = 1; sel[0] = 1; sel[1] = 0; sel[2] = 1; // { f = 1, a = b = c = d = e = g = h = 0 }
#(1) in = 1; sel[0] = 1; sel[1] = 1; sel[2] = 0; // { g = 1, a = b = c = d = e = f = h = 0 }
#(1) in = 1; sel[0] = 1; sel[1] = 1; sel[2] = 1; // { h = 1, a = b = c = d = e = f = g = 0 }
end
initial begin
$printtimescale;
// Time scale of (test) is 1s / 1s
$monitor ("%1d | in = %d | sel = [%d, %d, %d] | a = %d | b = %d | c = %d | d = %d | e = %d | f = %d | g = %d | h = %d", $time, in, sel[0], sel[1], sel[2], a, b, c, d, e, f, g, h);
// 0 | in = 1 | sel = [0, 0, 0] | a = 1 | b = 0 | c = 0 | d = 0 | e = 0 | f = 0 | g = 0 | h = 0
// 1 | in = 1 | sel = [0, 0, 1] | a = 0 | b = 1 | c = 0 | d = 0 | e = 0 | f = 0 | g = 0 | h = 0
// 2 | in = 1 | sel = [0, 1, 0] | a = 0 | b = 0 | c = 1 | d = 0 | e = 0 | f = 0 | g = 0 | h = 0
// 3 | in = 1 | sel = [0, 1, 1] | a = 0 | b = 0 | c = 0 | d = 1 | e = 0 | f = 0 | g = 0 | h = 0
// 4 | in = 1 | sel = [1, 0, 0] | a = 0 | b = 0 | c = 0 | d = 0 | e = 1 | f = 0 | g = 0 | h = 0
// 5 | in = 1 | sel = [1, 0, 1] | a = 0 | b = 0 | c = 0 | d = 0 | e = 0 | f = 1 | g = 0 | h = 0
// 6 | in = 1 | sel = [1, 1, 0] | a = 0 | b = 0 | c = 0 | d = 0 | e = 0 | f = 0 | g = 1 | h = 0
// 7 | in = 1 | sel = [1, 1, 1] | a = 0 | b = 0 | c = 0 | d = 0 | e = 0 | f = 0 | g = 0 | h = 1
end
endmodule
/*
DMux(in, sel) : If sel = 0 then { a = in, b = 0 } else { a = 0, b = in }
*/
// gate-level
module dmux_gate (output a, b, input in, sel);
// wire : internal pin
wire w1;
wire w2;
wire notsel;
// operations
not(notsel, sel);
and(a, in, notsel);
and(b, in, sel);
endmodule
// behavioural-level
module dmux_behavioural (output reg a, b, input in, sel);
always @ (in or sel) begin
// note: 1'b : 1 bit
if (sel == 1'b0) begin
a = in;
b = 1'b0;
end
else begin
a = 1'b0;
b = in;
end
end
endmodule
// test
module test;
reg in, sel;
wire a, b;
// dmux_gate Instance0 (a, b, in, sel);
dmux_behavioural Instance0 (a, b, in, sel);
// note: #(n) : delay by n timestep (check time scale with $printtimescale)
initial begin
#(0) in = 0; sel = 0; // 0, 0
#(1) in = 1; sel = 0; // 1, 0
#(1) in = 0; sel = 1; // 0, 0
#(1) in = 1; sel = 1; // 0, 1
end
initial begin
$printtimescale;
// Time scale of (test) is 1s / 1s
$monitor ("%1d | in = %d | sel = %d | a = %d | b = %d", $time, in, sel, a, b);
// 0 | in = 0 | sel = 0 | a = 0 | b = 0
// 1 | in = 1 | sel = 0 | a = 1 | b = 0
// 2 | in = 0 | sel = 1 | a = 0 | b = 0
// 3 | in = 1 | sel = 1 | a = 0 | b = 1
end
endmodule
/*
Mux4Way16(a, b, c, d, sel) :
If sel = 00 then out = a else if
sel = 01 then out = b else if
sel = 10 then out = c else if
sel = 11 then out = d
*/
// mux.v
module mux_gate (output out, input a, b, sel);
// wire : internal pin
wire w1;
wire w2;
wire notsel;
// operations
not(notsel, sel);
and(w1, a, notsel);
and(w2, b, sel);
or(out, w1, w2);
endmodule
// mux16.v
module mux16_gate (output [15:0] out, input [15:0] a, b, input sel);
mux_gate Instance0 (out[0], a[0], b[0], sel);
mux_gate Instance1 (out[1], a[1], b[1], sel);
mux_gate Instance2 (out[2], a[2], b[2], sel);
mux_gate Instance3 (out[3], a[3], b[3], sel);
mux_gate Instance4 (out[4], a[4], b[4], sel);
mux_gate Instance5 (out[5], a[5], b[5], sel);
mux_gate Instance6 (out[6], a[6], b[6], sel);
mux_gate Instance7 (out[7], a[7], b[7], sel);
mux_gate Instance8 (out[8], a[8], b[8], sel);
mux_gate Instance9 (out[9], a[9], b[9], sel);
mux_gate Instance10 (out[10], a[10], b[10], sel);
mux_gate Instance11 (out[11], a[11], b[11], sel);
mux_gate Instance12 (out[12], a[12], b[12], sel);
mux_gate Instance13 (out[13], a[13], b[13], sel);
mux_gate Instance14 (out[14], a[14], b[14], sel);
mux_gate Instance15 (out[15], a[15], b[15], sel);
endmodule
// gate-level
module mux4way16_gate (output [15:0] out, input [15:0] a, b, c, d, input [1:0] sel);
wire [15:0] ab, cd;
mux16_gate Instance0 (ab, a, b, sel[1]);
mux16_gate Instance1 (cd, c, d, sel[1]);
mux16_gate Instance2 (out, ab, cd, sel[0]);
endmodule
// behavioural-level
module mux4way16_behavioural (output reg [15:0] out, input [15:0] a, b, c, d, input [1:0] sel);
always @ (a or b or c or d or sel) begin
// note: 2'b : 2 bit
if (sel == 2'b00) begin
out = a;
end
else if (sel == 2'b10) begin
out = b;
end
else if (sel == 2'b01) begin
out = c;
end
else begin
out = d;
end
end
endmodule
// test
module test;
reg [15:0] a, b, c, d;
reg [1:0] sel;
wire [15:0] out;
// mux4way16_gate Instance0 (out, a, b, c, d, sel);
mux4way16_behavioural Instance0 (out, a, b, c, d, sel);
// note: #(n) : delay by n timestep (check time scale with $printtimescale)
initial begin
a[15:0] = 8'b11111111;
b[15:0] = 8'b00000000;
c[15:0] = 8'b11111111;
d[15:0] = 8'b00000000;
#(0) sel[0] = 0; sel[1] = 0; // out = a = 1
#(1) sel[0] = 0; sel[1] = 1; // out = b = 0
#(1) sel[0] = 1; sel[1] = 0; // out = c = 1
#(1) sel[0] = 1; sel[1] = 1; // out = d = 0
end
initial begin
$printtimescale;
// Time scale of (test) is 1s / 1s
$monitor ("%2d | a = %d | b = %d | c = %d | d = %d | sel = [%d, %d] | out = %d", $time, a[0], b[0], c[0], d[0], sel[0], sel[1], out[0]);
// 0 | a = 1 | b = 0 | c = 1 | d = 0 | sel = [0, 0] | out = 1
// 1 | a = 1 | b = 0 | c = 1 | d = 0 | sel = [0, 1] | out = 0
// 2 | a = 1 | b = 0 | c = 1 | d = 0 | sel = [1, 0] | out = 1
// 3 | a = 1 | b = 0 | c = 1 | d = 0 | sel = [1, 1] | out = 0
end
endmodule
/*
Mux8Way16(a, b, c, d, e, f, g, h, sel) :
If sel = 000 then out = a else if
sel = 001 then out = b else if
sel = 010 then out = c else if
sel = 011 then out = d else if
sel = 100 then out = e else if
sel = 101 then out = f else if
sel = 110 then out = g else if
sel = 111 then out = h
*/
// mux.v
module mux_gate (output out, input a, b, sel);
// wire : internal pin
wire w1;
wire w2;
wire notsel;
// operations
not(notsel, sel);
and(w1, a, notsel);
and(w2, b, sel);
or(out, w1, w2);
endmodule
// mux16.v
module mux16_gate (output [15:0] out, input [15:0] a, b, input sel);
mux_gate Instance0 (out[0], a[0], b[0], sel);
mux_gate Instance1 (out[1], a[1], b[1], sel);
mux_gate Instance2 (out[2], a[2], b[2], sel);
mux_gate Instance3 (out[3], a[3], b[3], sel);
mux_gate Instance4 (out[4], a[4], b[4], sel);
mux_gate Instance5 (out[5], a[5], b[5], sel);
mux_gate Instance6 (out[6], a[6], b[6], sel);
mux_gate Instance7 (out[7], a[7], b[7], sel);
mux_gate Instance8 (out[8], a[8], b[8], sel);
mux_gate Instance9 (out[9], a[9], b[9], sel);
mux_gate Instance10 (out[10], a[10], b[10], sel);
mux_gate Instance11 (out[11], a[11], b[11], sel);
mux_gate Instance12 (out[12], a[12], b[12], sel);
mux_gate Instance13 (out[13], a[13], b[13], sel);
mux_gate Instance14 (out[14], a[14], b[14], sel);
mux_gate Instance15 (out[15], a[15], b[15], sel);
endmodule
// gate-level
module mux8way16_gate (output [15:0] out, input [15:0] a, b, c, d, e, f, g, h, input [2:0] sel);
wire [15:0] ab, cd, ef, gh, abcd, efgh;
mux16_gate Instance0 (ab, a, b, sel[2]);
mux16_gate Instance1 (cd, c, d, sel[2]);
mux16_gate Instance2 (ef, e, f, sel[2]);
mux16_gate Instance3 (gh, g, h, sel[2]);
mux16_gate Instance4 (abcd, ab, cd, sel[1]);
mux16_gate Instance5 (efgh, ef, gh, sel[1]);
mux16_gate Instance6 (out, abcd, efgh, sel[0]);
endmodule
// behavioural-level
module mux8way16_behavioural (output reg [15:0] out, input [15:0] a, b, c, d, e, f, g, h, input [2:0] sel);
always @ (a or b or c or d or sel) begin
// note: 3'b : 3 bit
if (sel == 3'b000) begin
out = a;
end
else if (sel == 3'b100) begin
out = b;
end
else if (sel == 3'b010) begin
out = c;
end
else if (sel == 3'b110) begin
out = d;
end
else if (sel == 3'b001) begin
out = e;
end
else if (sel == 3'b101) begin
out = f;
end
else if (sel == 3'b011) begin
out = g;
end
else begin
out = h;
end
end
endmodule
// test
module test;
reg [15:0] a, b, c, d, e, f, g, h;
reg [2:0] sel;
wire [15:0] out;
// mux8way16_gate Instance0 (out, a, b, c, d, e, f, g, h, sel);
mux8way16_behavioural Instance0 (out, a, b, c, d, e, f, g, h, sel);
// note: #(n) : delay by n timestep (check time scale with $printtimescale)
initial begin
a[15:0] = 8'b11111111;
b[15:0] = 8'b00000000;
c[15:0] = 8'b11111111;
d[15:0] = 8'b00000000;
e[15:0] = 8'b11111111;
f[15:0] = 8'b00000000;
g[15:0] = 8'b11111111;
h[15:0] = 8'b00000000;
#(0) sel[0] = 0; sel[1] = 0; sel[2] = 0; // out = a = 1
#(1) sel[0] = 0; sel[1] = 0; sel[2] = 1; // out = b = 0
#(1) sel[0] = 0; sel[1] = 1; sel[2] = 0; // out = c = 1
#(1) sel[0] = 0; sel[1] = 1; sel[2] = 1; // out = d = 0
#(1) sel[0] = 1; sel[1] = 0; sel[2] = 0; // out = e = 1
#(1) sel[0] = 1; sel[1] = 0; sel[2] = 1; // out = f = 0
#(1) sel[0] = 1; sel[1] = 1; sel[2] = 0; // out = g = 1
#(1) sel[0] = 1; sel[1] = 1; sel[2] = 1; // out = h = 0
end
initial begin
$printtimescale;
// Time scale of (test) is 1s / 1s
$monitor ("%2d | a = %d | b = %d | c = %d | d = %d | e = %d | f = %d | g = %d | h = %d | sel = [%d, %d, %d] | out = %d", $time, a[0], b[0], c[0], d[0], e[0], f[0], g[0], h[0], sel[0], sel[1], sel[2], out[0]);
// 0 | a = 1 | b = 0 | c = 1 | d = 0 | e = 1 | f = 0 | g = 1 | h = 0 | sel = [0, 0, 0] | out = 1
// 1 | a = 1 | b = 0 | c = 1 | d = 0 | e = 1 | f = 0 | g = 1 | h = 0 | sel = [0, 0, 1] | out = 0
// 2 | a = 1 | b = 0 | c = 1 | d = 0 | e = 1 | f = 0 | g = 1 | h = 0 | sel = [0, 1, 0] | out = 1
// 3 | a = 1 | b = 0 | c = 1 | d = 0 | e = 1 | f = 0 | g = 1 | h = 0 | sel = [0, 1, 1] | out = 0
// 4 | a = 1 | b = 0 | c = 1 | d = 0 | e = 1 | f = 0 | g = 1 | h = 0 | sel = [1, 0, 0] | out = 1
// 5 | a = 1 | b = 0 | c = 1 | d = 0 | e = 1 | f = 0 | g = 1 | h = 0 | sel = [1, 0, 1] | out = 0
// 6 | a = 1 | b = 0 | c = 1 | d = 0 | e = 1 | f = 0 | g = 1 | h = 0 | sel = [1, 1, 0] | out = 1
// 7 | a = 1 | b = 0 | c = 1 | d = 0 | e = 1 | f = 0 | g = 1 | h = 0 | sel = [1, 1, 1] | out = 0
end
endmodule
/*
Mux16(a, b, sel) : If sel = 0 then for i = 0..15 out[i] = a[i] else for i = 0..15 out[i] = b[i]
*/
// mux.v
module mux_gate (output out, input a, b, sel);
// wire : internal pin
wire w1;
wire w2;
wire notsel;
// operations
not(notsel, sel);
and(w1, a, notsel);
and(w2, b, sel);
or(out, w1, w2);
endmodule
// gate-level
module mux16_gate (output [15:0] out, input [15:0] a, b, input sel);
mux_gate Instance0 (out[0], a[0], b[0], sel);
mux_gate Instance1 (out[1], a[1], b[1], sel);
mux_gate Instance2 (out[2], a[2], b[2], sel);
mux_gate Instance3 (out[3], a[3], b[3], sel);
mux_gate Instance4 (out[4], a[4], b[4], sel);
mux_gate Instance5 (out[5], a[5], b[5], sel);
mux_gate Instance6 (out[6], a[6], b[6], sel);
mux_gate Instance7 (out[7], a[7], b[7], sel);
mux_gate Instance8 (out[8], a[8], b[8], sel);
mux_gate Instance9 (out[9], a[9], b[9], sel);
mux_gate Instance10 (out[10], a[10], b[10], sel);
mux_gate Instance11 (out[11], a[11], b[11], sel);
mux_gate Instance12 (out[12], a[12], b[12], sel);
mux_gate Instance13 (out[13], a[13], b[13], sel);
mux_gate Instance14 (out[14], a[14], b[14], sel);
mux_gate Instance15 (out[15], a[15], b[15], sel);
endmodule
// behavioural-level
module mux16_behavioural (output reg [15:0] out, input [15:0] a, b, input sel);
always @ (a or b or sel) begin
// note: 1'b : 1 bit
if (sel == 1'b0) begin
out = a;
end
else begin
out = b;
end
end
endmodule
// test
module test;
reg [15:0] a, b;
reg sel;
wire [15:0] out;
// mux16_gate Instance0 (out, a, b, sel);
mux16_behavioural Instance0 (out, a, b, sel);
// note: #(n) : delay by n timestep (check time scale with $printtimescale)
initial begin
#(0) a[15:0] = 8'b11111111; b[15:0] = 8'b00000000; sel = 0; // out = 1
#(1) a[15:0] = 8'b11111111; b[15:0] = 8'b00000000; sel = 1; // out = 0
end
initial begin
$printtimescale;
// Time scale of (test) is 1s / 1s
$monitor ("%2d | a = %d | b = %d | sel = %d | out = %d", $time, a[0], b[0], sel, out[0]);
// 0 | a = 1 | b = 0 | sel = 0 | out = 1
// 1 | a = 1 | b = 0 | sel = 1 | out = 0
end
endmodule
/*
Mux(a, b, sel) : If sel = 0 then out = a else out = b
*/
// gate-level
module mux_gate (output out, input a, b, sel);
// wire : internal pin
wire w1;
wire w2;
wire notsel;
// operations
not(notsel, sel);
and(w1, a, notsel);
and(w2, b, sel);
or(out, w1, w2);
endmodule
// behavioural-level
module mux_behavioural (output reg out, input a, b, sel);
always @ (a or b or sel) begin
// note: 1'b : 1 bit
if (sel == 1'b0) begin
out = a;
end
else begin
out = b;
end
end
endmodule
// test
module test;
reg a, b, sel;
wire out;
// mux_gate Instance0 (out, a, b, sel);
mux_behavioural Instance0 (out, a, b, sel);
// note: #(n) : delay by n timestep (check time scale with $printtimescale)
initial begin
#(0) a = 0; b = 0; sel = 0; // 0
#(1) a = 0; b = 1; sel = 0; // 0
#(1) a = 1; b = 0; sel = 0; // 1
#(1) a = 1; b = 1; sel = 0; // 1
#(1) a = 0; b = 0; sel = 1; // 0
#(1) a = 0; b = 1; sel = 1; // 1
#(1) a = 1; b = 0; sel = 1; // 0
#(1) a = 1; b = 1; sel = 1; // 1
end
initial begin
$printtimescale;
// Time scale of (test) is 1s / 1s
$monitor ("%1d | a = %d | b = %d | sel = %d | out = %d", $time, a, b, sel, out);
// 0 | a = 0 | b = 0 | sel = 0 | out = 0
// 1 | a = 0 | b = 1 | sel = 0 | out = 0
// 2 | a = 1 | b = 0 | sel = 0 | out = 1
// 3 | a = 1 | b = 1 | sel = 0 | out = 1
// 4 | a = 0 | b = 0 | sel = 1 | out = 0
// 5 | a = 0 | b = 1 | sel = 1 | out = 1
// 6 | a = 1 | b = 0 | sel = 1 | out = 0
// 7 | a = 1 | b = 1 | sel = 1 | out = 1
end
endmodule
/*
Nand(a, b) : If a = b = 1 then out = 0 else out = 1
*/
// gate-level
module nand_gate (output out, input a, b);
// wire : internal pin
wire w;
// operations
and(w, a, b);
not(out, w);
endmodule
// behavioural-level
module nand_behavioural (output reg out, input a, b);
always @ (a or b) begin
// note: 1'b : 1 bit
if (a == 1'b1 & b == 1'b1) begin
out = 1'b0;
end
else begin
out = 1'b1;
end
end
endmodule
// test
module test;
reg a, b;
wire out;
// nand_gate Instance0 (out, a, b);
nand_behavioural Instance0 (out, a, b);
// note: #(n) : delay by n timestep (check time scale with $printtimescale)
initial begin
#(0) a = 0; b = 0; // 1
#(1) a = 0; b = 1; // 1
#(1) a = 1; b = 0; // 1
#(1) a = 1; b = 1; // 0
end
initial begin
$printtimescale;
// Time scale of (_nand_test) is 1s / 1s
$monitor ("%1d | a = %d | b = %d | out = %d", $time, a, b, out);
// 0 | a = 0 | b = 0 | out = 1
// 1 | a = 0 | b = 1 | out = 1
// 2 | a = 1 | b = 0 | out = 1
// 3 | a = 1 | b = 1 | out = 0
end
endmodule
/*
Not16(in) : For i = 0..15 out[i] = Not(in[i])
*/
// gate-level
module not16_gate (output [15:0] out, input [15:0] in);
// operations
not(out[0], in[0]);
not(out[1], in[1]);
not(out[2], in[2]);
not(out[3], in[3]);
not(out[4], in[4]);
not(out[5], in[5]);
not(out[6], in[6]);
not(out[7], in[7]);
not(out[8], in[8]);
not(out[9], in[9]);
not(out[10], in[10]);
not(out[11], in[11]);
not(out[12], in[12]);
not(out[13], in[13]);
not(out[14], in[14]);
not(out[15], in[15]);
endmodule
// behavioural-level
module not16_behavioural (output reg [15:0] out, input [15:0] in);
always @ (in) begin
out = ~in;
end
endmodule
// test
module test;
reg [15:0] in;
wire [15:0] out;
// not16_gate Instance0 (out, in);
not16_behavioural Instance0 (out, in);
// note: #(n) : delay by n timestep (check time scale with $printtimescale)
initial begin
in[7:0] = 8'b11111111; // 0, 0, 0, 0, 0, 0, 0, 0
in[15:8] = 8'b00000000; // 1, 1, 1, 1, 1, 1, 1, 1
end
initial begin
$printtimescale;
// Time scale of (test) is 1s / 1s
#(0) $monitor ("%2d | in = %d | out = %d", $time, in[0], out[0]);
#(1) $monitor ("%2d | in = %d | out = %d", $time, in[1], out[1]);
#(1) $monitor ("%2d | in = %d | out = %d", $time, in[2], out[2]);
#(1) $monitor ("%2d | in = %d | out = %d", $time, in[3], out[3]);
#(1) $monitor ("%2d | in = %d | out = %d", $time, in[4], out[4]);
#(1) $monitor ("%2d | in = %d | out = %d", $time, in[5], out[5]);
#(1) $monitor ("%2d | in = %d | out = %d", $time, in[6], out[6]);
#(1) $monitor ("%2d | in = %d | out = %d", $time, in[7], out[7]);
#(1) $monitor ("%2d | in = %d | out = %d", $time, in[8], out[8]);
#(1) $monitor ("%2d | in = %d | out = %d", $time, in[9], out[9]);
#(1) $monitor ("%2d | in = %d | out = %d", $time, in[10], out[10]);
#(1) $monitor ("%2d | in = %d | out = %d", $time, in[11], out[11]);
#(1) $monitor ("%2d | in = %d | out = %d", $time, in[12], out[12]);
#(1) $monitor ("%2d | in = %d | out = %d", $time, in[13], out[13]);
#(1) $monitor ("%2d | in = %d | out = %d", $time, in[14], out[14]);
#(1) $monitor ("%2d | in = %d | out = %d", $time, in[15], out[15]);
// 0 | in = 1 | out = 0
// 1 | in = 1 | out = 0
// 2 | in = 1 | out = 0
// 3 | in = 1 | out = 0
// 4 | in = 1 | out = 0
// 5 | in = 1 | out = 0
// 6 | in = 1 | out = 0
// 7 | in = 1 | out = 0
// 8 | in = 0 | out = 1
// 9 | in = 0 | out = 1
// 10 | in = 0 | out = 1
// 11 | in = 0 | out = 1
// 12 | in = 0 | out = 1
// 13 | in = 0 | out = 1
// 14 | in = 0 | out = 1
// 15 | in = 0 | out = 1
end
endmodule
/*
Not(in) : If in = 0 then out = 1 else out = 0
*/
// gate-level
module not_gate (output out, input in);
// operations (note: limited to nand-gates)
nand(out, in, in);
endmodule
// test
module test;
reg in;
wire out;
not_gate Instance0 (out, in);
// note: #(n) : delay by n timestep (check time scale with $printtimescale)
initial begin
#(0) in = 0; // 1
#(1) in = 1; // 0
end
initial begin
$printtimescale;
// Time scale of (_nand_test) is 1s / 1s
$monitor ("%1d | in = %d | out = %d", $time, in, out);
// 0 | in = 0 | out = 1
// 1 | in = 1 | out = 0
end
endmodule
/*
Or8Way(in) : out = Or(in[0], ..., in[7])
*/
// gate-level
module or8way_gate (output out, input [7:0] in);
// operations : or
or(out, in[0], in[1], in[2], in[3], in[4], in[5], in[6], in[7]);
endmodule
// behavioural-level
module or8way_behavioural (output reg out, input [7:0] in);
always @ (in) begin
out = in[0] | in[1] | in[2] | in[3] | in[4] | in[5] | in[6] | in[7];
end
endmodule
// test
module test;
reg [7:0] in;
wire out;
// or8way_gate Instance0 (out, in);
or8way_behavioural Instance0 (out, in);
// note: #(n) : delay by n timestep (check time scale with $printtimescale)
initial begin
#(0) in[0] = 1; in[1] = 0; in[2] = 1; in[3] = 0; in[4] = 1; in[5] = 0; in[6] = 1; in[7] = 0; // out = 1
#(1) in[0] = 0; in[1] = 0; in[2] = 0; in[3] = 0; in[4] = 0; in[5] = 0; in[6] = 0; in[7] = 0; // out = 0
end
initial begin
$printtimescale;
// Time scale of (_nand_test) is 1s / 1s
$monitor ("%1d | in = [%d, %d, %d, %d, %d, %d, %d, %d] | out = %d", $time, in[0], in[1], in[2], in[3], in[4], in[5], in[6], in[7], out);
// 0 | in = [1, 0, 1, 0, 1, 0, 1, 0] | out = 1
// 1 | in = [0, 0, 0, 0, 0, 0, 0, 0] | out = 0
end
endmodule
/*
Or16(a, b) : For i = 0..15 out[i] = Or(a[i], b[i])
*/
// gate-level
module or16_gate (output [15:0] out, input [15:0] a, b);
// operations
or(out[0], a[0], b[0]);
or(out[1], a[1], b[1]);
or(out[2], a[2], b[2]);
or(out[3], a[3], b[3]);
or(out[4], a[4], b[4]);
or(out[5], a[5], b[5]);
or(out[6], a[6], b[6]);
or(out[7], a[7], b[7]);
or(out[8], a[8], b[8]);
or(out[9], a[9], b[9]);
or(out[10], a[10], b[10]);
or(out[11], a[11], b[11]);
or(out[12], a[12], b[12]);
or(out[13], a[13], b[13]);
or(out[14], a[14], b[14]);
or(out[15], a[15], b[15]);
endmodule
// behavioural-level
module or16_behavioural (output reg [15:0] out, input [15:0] a, b);
always @ (a or b) begin
out = a | b;
end
endmodule
// test
module test;
reg [15:0] a, b;
wire [15:0] out;
// or16_gate Instance0 (out, a, b);
or16_behavioural Instance0 (out, a, b);
// note: #(n) : delay by n timestep (check time scale with $printtimescale)
initial begin
a[7:0] = 8'b11111111; b[7:0] = 8'b00000000; // 1, 1, 1, 1, 1, 1, 1, 1
a[15:8] = 8'b00000000; b[15:8] = 8'b00000000; // 0, 0, 0, 0, 0, 0, 0, 0
end
initial begin
$printtimescale;
// Time scale of (test) is 1s / 1s
#(0) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[0], b[0], out[0]);
#(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[1], b[1], out[1]);
#(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[2], b[2], out[2]);
#(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[3], b[3], out[3]);
#(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[4], b[4], out[4]);
#(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[5], b[5], out[5]);
#(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[6], b[6], out[6]);
#(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[7], b[7], out[7]);
#(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[8], b[8], out[8]);
#(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[9], b[9], out[9]);
#(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[10], b[10], out[10]);
#(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[11], b[11], out[11]);
#(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[12], b[12], out[12]);
#(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[13], b[13], out[13]);
#(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[14], b[14], out[14]);
#(1) $monitor ("%2d | a = %d | b = %d | out = %d", $time, a[15], b[15], out[15]);
// 0 | a = 1 | b = 0 | out = 1
// 1 | a = 1 | b = 0 | out = 1
// 2 | a = 1 | b = 0 | out = 1
// 3 | a = 1 | b = 0 | out = 1
// 4 | a = 1 | b = 0 | out = 1
// 5 | a = 1 | b = 0 | out = 1
// 6 | a = 1 | b = 0 | out = 1
// 7 | a = 1 | b = 0 | out = 1
// 8 | a = 0 | b = 0 | out = 0
// 9 | a = 0 | b = 0 | out = 0
// 10 | a = 0 | b = 0 | out = 0
// 11 | a = 0 | b = 0 | out = 0
// 12 | a = 0 | b = 0 | out = 0
// 13 | a = 0 | b = 0 | out = 0
// 14 | a = 0 | b = 0 | out = 0
// 15 | a = 0 | b = 0 | out = 0
end
endmodule
/*
Or(a, b) : If a = b = 0 then out = 0 else out = 1
*/
// gate-level
module or_gate (output out, input a, b);
// wire : internal pin
wire w1, w2;
// operations (note: limited to nand-gates)
nand(w1, a, a);
nand(w2, b, b);
nand(out, w1, w2);
endmodule
// test
module test;
reg a, b;
wire out;
or_gate Instance0 (out, a, b);
// note: #(n) : delay by n timestep (check time scale with $printtimescale)
initial begin
#(0) a = 0; b = 0; // out = 0
#(1) a = 0; b = 1; // out = 1
#(1) a = 1; b = 0; // out = 1
#(1) a = 1; b = 1; // out = 1
end
initial begin
$printtimescale;
// Time scale of (_nand_test) is 1s / 1s
$monitor ("%1d | a = %d | b = %d | out = %d", $time, a, b, out);
// 0 | a = 0 | b = 0 | out = 0
// 1 | a = 0 | b = 1 | out = 1
// 2 | a = 1 | b = 0 | out = 1
// 3 | a = 1 | b = 1 | out = 1
end
endmodule
/*
Xor(a, b) : If a<>b then out = 1 else out = 0
*/
// gate-level
module xor_gate (output out, input a, b);
// wire : internal pin
wire w1;
wire w2;
wire nota;
wire notb;
// operations
not(nota, a);
not(notb, b);
and(w1, a, notb);
and(w2, nota, b);
or(out, w1, w2);
endmodule
// behavioural-level
module xor_behavioural (output reg out, input a, b);
always @ (a or b) begin
// note: 1'b : 1 bit
if ((a == 1'b1 & b == 1'b0) | (a == 1'b0 & b == 1'b1)) begin
out = 1'b1;
end
else begin
out = 1'b0;
end
end
endmodule
// test
module test;
reg a, b;
wire out;
// xor_gate Instance0 (out, a, b);
xor_behavioural Instance0 (out, a, b);
// note: #(n) : delay by n timestep (check time scale with $printtimescale)
initial begin
#(0) a = 0; b = 0; // 0
#(1) a = 0; b = 1; // 1
#(1) a = 1; b = 0; // 1
#(1) a = 1; b = 1; // 0
end
initial begin
$printtimescale;
// Time scale of (test) is 1s / 1s
$monitor ("%1d | a = %d | b = %d | out = %d", $time, a, b, out);
// 0 | a = 0 | b = 0 | out = 0
// 1 | a = 0 | b = 1 | out = 1
// 2 | a = 1 | b = 0 | out = 1
// 3 | a = 1 | b = 1 | out = 0
end
endmodule
goto_in_c.cheader-files.clinked-list.cmacros.cmemory.cpointers.cvalist.c
#include <stdio.h>
#define A 1
#define B 0
#define C 0
int main() {
// fail switch
if (!A) {
goto exit;
}
if (!B) {
goto restart_B;
}
if (!C) {
goto restart_C;
}
// no fails
return 0;
restart_B:
printf("%s\n", "restarting B");
restart_C:
printf("%s\n", "restarting C");
exit:
printf("%s\n", "exiting");
// some fails
return -1;
}
#include <stdio.h>
// filename.h
/*
#ifndef FILENAME_H
#define FILENAME_H
const int number = 10;
#endif
*/
#include "filename.h"
int main() {
printf("%d\n", number); // 10
}
// linked list implementation in C
#include <stdio.h>
#include <stdlib.h>
// element is struct with a value and a pointer to the next element
struct Element {
int value;
struct Element *next;
};
// allocate memory for element
struct Element *create_element(int value) {
struct Element *element = (struct Element*) malloc(sizeof(struct Element));
element->value = value;
element->next = NULL;
return element;
}
// insert
void ll_insert(struct Element **element, int value) {
struct Element *new_element = create_element(value);
// list is empty
if (*element == NULL) { *element = new_element; }
// list is not empty
else {
struct Element *current = *element;
// iterate until last element
while (current->next != NULL) {
current = current->next;
}
// insert new element
current->next = new_element;
}
}
// remove
void ll_remove(struct Element **element, int value) {
struct Element *current = *element;
struct Element *previous = NULL;
// iterate until last element
while (current != NULL) {
// value is found
if (current->value == value) {
// value is first element
if (previous == NULL) {
*element = current->next;
}
// value is not first element
else {
previous->next = current->next;
}
// free memory
free(current);
return;
}
// update pointers
previous = current;
current = current->next;
}
}
// print
void print(struct Element *element) {
struct Element *current = element;
// iterate until last element
while (current != NULL) {
printf("%d\n", current->value);
current = current->next;
}
}
int main() {
struct Element *ll = NULL;
// insert
ll_insert(&ll, 5);
ll_insert(&ll, 10);
ll_insert(&ll, 15);
ll_insert(&ll, 20);
ll_insert(&ll, 25);
ll_insert(&ll, 30);
print(ll); // 5 10 15 20 25 30
// remove
ll_remove(&ll, 15);
ll_remove(&ll, 30);
print(ll); // 5 10 20 25
}
#include <stdio.h>
#include <stddef.h>
// stringify error messages
#define error_message(error) \
printf("error: " #error "\n")
// if not defined (used in header files to avoid multiple inclusion)
#ifndef MESSAGE
#define MESSAGE "This is the message if not already defined."
#endif
// parameterized macros
#define square(x) ((x) * (x))
#define max(x, y) ((x) > (y) ? (x) : (y))
int main() {
printf("%s\n", __FILE__); // macros.c
printf("%s\n", __DATE__); // Aug 21 2019
printf("%s\n", __TIME__); // 01:22:18
printf("%d\n", __LINE__); // 12
printf("%d\n", __STDC__); // 1
error_message("This is an error.");
// error: "This is an error."
printf("%s\n", MESSAGE);
// This is the message if not already defined.
printf("%d\n", square(2)); // 4
printf("%d\n", max(4,5)); // 5
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/*
- allocate an array of n elements of size s
void *calloc(int n, int s);
- release a block of memory at address
void free(void *address);
- allocate an array of b bytes (uninitialised)
void *malloc(int b);
- re-allocate memory at address (extending to new size s)
void *realloc(void *address, int s);
*/
int main() {
char name[36];
char *description; // pointer to char without size limit
// copy string of 35 bytes into buffer of 36 bytes
strcpy(name, "Wolfeschlegelsteinhausenbergerdorff");
// allocate memory dynamically (can result in fragmented memory)
// description = malloc(10 * sizeof(char));
// strcpy(description, "A too long text to store in only 10 bytes...");
// printf("%s\n", description);
// malloc(): corrupted top size
// Aborted
description = malloc(100 * sizeof(char));
strcpy(description, "A too long text to store in only 10 bytes...");
printf("%s\n", description);
// A too long text to store in only 10 bytes...
// free memory
free(description);
}
#include <stdio.h>
#include <stddef.h>
int main() {
int num = 5;
int *ip = NULL; // null pointer
printf("%p\n", ip); // 0x0 (nil)
// point to address of num
ip = #
printf("%p\n", &num); // 0x7ffdb78c2664
printf("%p\n", ip); // 0x7ffdb78c2664
// dereference (get value at address)
printf("%d\n", *ip); // 5
}
#include <stdio.h>
#include <stdarg.h>
// declare function (normally in header file)
double average(int n, ...);
// define function
double average(int n, ...) {
va_list valist; /* stdarg.h */
// return value
double sum = 0.0;
// init valist for n arguments
va_start(valist, n);
// access arguments
for (int i=0; i<n; i++) {
sum += va_arg(valist, int);
}
// free memory
va_end(valist);
// success
return sum / n;
}
int main() {
printf("average of {1,2,3,4,5}: %f\n", average(5, 1, 2, 3, 4, 5));
// average of {1,2,3,4,5}: 3.000000
}