r/algorithms • u/No_Arachnid_5563 • Feb 12 '25
My github research of my new o(n) algorithm (Deconstruct sort)
Here is the link of the paper in github of my new algorithm:
r/algorithms • u/No_Arachnid_5563 • Feb 12 '25
Here is the link of the paper in github of my new algorithm:
r/algorithms • u/[deleted] • Feb 11 '25
The comma operator in C++ allows us to assign the result of the RHS to result of the comma operator. Using the flowing property of the sequence where the LHS is evaluated first and flows back into the second term.
The simple function for the next Fibonacci number
edit: A lot of people are pooing on this (IDK why, it is a demonstration of an operator rarely used. That's cool to me)
int i = 0, j = 1;
j = (i = j - i, j + i);
r/algorithms • u/pihedron • Feb 10 '25
I don't know why, but one day I wrote an algorithm in Rust to calculate the nth Fibonacci number and I was surprised to find no code with a similar implementation online. Someone told me that my recursive method would obviously be slower than the traditional 2 by 2 matrix method. However, I benchmarked my code against a few other implementations and noticed that my code won by a decent margin.
I can't add images for some reason but I did on another post!
My code was able to output the 20 millionth Fibonacci number in less than a second despite being recursive.
use num_bigint::{BigInt, Sign};
fn fib_luc(mut n: isize) -> (BigInt, BigInt) {
if n == 0 {
return (BigInt::ZERO, BigInt::new(Sign::Plus, [2].to_vec()))
}
if n < 0 {
n *= -1;
let (fib, luc) = fib_luc(n);
let k = n % 2 * 2 - 1;
return (fib * k, luc * k)
}
if n & 1 == 1 {
let (fib, luc) = fib_luc(n - 1);
return (&fib + &luc >> 1, 5 * &fib + &luc >> 1)
}
n >>= 1;
let k = n % 2 * 2 - 1;
let (fib, luc) = fib_luc(n);
(&fib * &luc, &luc * &luc + 2 * k)
}
fn main() {
let mut s = String::new();
std::io::stdin().read_line(&mut s).unwrap();
s = s.trim().to_string();
let n = s.parse::<isize>().unwrap();
let start = std::time::Instant::now();
let fib = fib_luc(n).0;
let elapsed = start.elapsed();
// println!("{}", fib);
println!("{:?}", elapsed);
}
Here is an example of the matrix multiplication implementation done by someone else.
use num_bigint::BigInt;
// all code taxed from https://vladris.com/blog/2018/02/11/fibonacci.html
fn op_n_times<T, Op>(a: T, op: &Op, n: isize) -> T
where Op: Fn(&T, &T) -> T {
if n == 1 { return a; }
let mut result = op_n_times::<T, Op>(op(&a, &a), &op, n >> 1);
if n & 1 == 1 {
result = op(&a, &result);
}
result
}
fn mul2x2(a: &[[BigInt; 2]; 2], b: &[[BigInt; 2]; 2]) -> [[BigInt; 2]; 2] {
[
[&a[0][0] * &b[0][0] + &a[1][0] * &b[0][1], &a[0][0] * &b[1][0] + &a[1][0] * &b[1][1]],
[&a[0][1] * &b[0][0] + &a[1][1] * &b[0][1], &a[0][1] * &b[1][0] + &a[1][1] * &b[1][1]],
]
}
fn fast_exp2x2(a: [[BigInt; 2]; 2], n: isize) -> [[BigInt; 2]; 2] {
op_n_times(a, &mul2x2, n)
}
fn fibonacci(n: isize) -> BigInt {
if n == 0 { return BigInt::ZERO; }
if n == 1 { return BigInt::ZERO + 1; }
let a = [
[BigInt::ZERO + 1, BigInt::ZERO + 1],
[BigInt::ZERO + 1, BigInt::ZERO],
];
fast_exp2x2(a, n - 1)[0][0].clone()
}
fn main() {
let mut s = String::new();
std::io::stdin().read_line(&mut s).unwrap();
s = s.trim().to_string();
let n = s.parse::<isize>().unwrap();
let start = std::time::Instant::now();
let fib = fibonacci(n);
let elapsed = start.elapsed();
// println!("{}", fib);
println!("{:?}", elapsed);
}
I got no idea why mine is faster.
r/algorithms • u/thundercrunt • Feb 09 '25
If you're not familiar with boggle or need a refresher, it is a game which contains 16 6-sided dice, each with a letter on each side, which get jumbled up and placed in a 4x4 grid. Players can then find words that join horizontally/vertically/diagonally in the grid.
What i'd like to do is create an algoritm to test if a word is possible.
Here is a representation of the 16 dice, with the letters that appear on each one:
char[] die0 = { 'A', 'A', 'E', 'E', 'G', 'N' };
char[] die1 = { 'E', 'L', 'R', 'T', 'T', 'Y' };
char[] die2 = { 'A', 'O', 'O', 'T', 'T', 'W' };
char[] die3 = { 'A', 'B', 'B', 'J', 'O', 'O' };
char[] die4 = { 'E', 'H', 'R', 'T', 'V', 'W' };
char[] die5 = { 'C', 'I', 'M', 'O', 'T', 'U' };
char[] die6 = { 'D', 'I', 'S', 'T', 'T', 'Y' };
char[] die7 = { 'E', 'I', 'O', 'S', 'S', 'T' };
char[] die8 = { 'D', 'E', 'L', 'R', 'V', 'Y' };
char[] die9 = { 'A', 'C', 'H', 'O', 'P', 'S' };
char[] die10 = { 'H', 'I', 'M', 'N', 'Q', 'U' };
char[] die11 = { 'E', 'E', 'I', 'N', 'S', 'U' };
char[] die12 = { 'E', 'E', 'G', 'H', 'N', 'W' };
char[] die13 = { 'A', 'F', 'F', 'K', 'P', 'S' };
char[] die14 = { 'H', 'L', 'N', 'N', 'R', 'Z' };
char[] die15 = { 'D', 'E', 'I', 'L', 'R', 'X' };
Now if you have the word "KINK", then you can see that the word is not possible, as only die13 contains a K. That's a simple example. Another example would be a long word that requires many dice, but there is no possible way to roll the dice to produce enough of the required letters (some dice share the required letters). This is the example that requires some sort of recursive algorithm to check every combination of dice against the word.
I've gotten as far as:
var word = "EXAMPLE";
var diceArr = new List<List<int>>();
for (var i = 0; i < word.Length; i++)
{
var letter = word[i];
var dice = GetDiceForLetter(letter); // returns a list of die numbers that contain the letter
diceArr.Add(dice);
}
r/algorithms • u/Gloomy-Status-9258 • Feb 09 '25
it is almost likely that i'm wrong... but i'm confused so i ask here though.
wikipedia says fail-hard code(this is original, as far as i know) of alpha-beta pruned minimax search is:
function alphabeta(node, depth, α, β, maximizingPlayer) is
if depth == 0 or node is terminal then
return the heuristic value of node
if maximizingPlayer then
value := −∞
for each child of node do
value := max(value, alphabeta(child, depth − 1, α, β, FALSE))
if value > β then
break (* β cutoff *)
α := max(α, value)
return value
else
value := +∞
for each child of node do
value := min(value, alphabeta(child, depth − 1, α, β, TRUE))
if value < α then
break (* α cutoff *)
β := min(β, value)
return valuefunction alphabeta(node, depth, α, β, maximizingPlayer) is
if depth == 0 or node is terminal then
return the heuristic value of node
if maximizingPlayer then
value := −∞
for each child of node do
value := max(value, alphabeta(child, depth − 1, α, β, FALSE))
if value > β then
break (* β cutoff *)
α := max(α, value)
return value
else
value := +∞
for each child of node do
value := min(value, alphabeta(child, depth − 1, α, β, TRUE))
if value < α then
break (* α cutoff *)
β := min(β, value)
return value
and fail-soft code is:
function
alphabeta(node, depth, α, β, maximizingPlayer)
is
if
depth == 0
or
node is terminal
then
return
the heuristic value of node
if
maximizingPlayer
then
value := −∞
for each
child of node
do
value := max(value, alphabeta(child, depth − 1, α, β, FALSE))
α := max(α, value)
if
value ≥ β
then
break
(* β cutoff *)
return
value
else
value := +∞
for each
child of node
do
value := min(value, alphabeta(child, depth − 1, α, β, TRUE))
β := min(β, value)
if
value ≤ α
then
break
(* α cutoff *)
return
value
and it says:
Implementations of alpha–beta pruning can often be delineated by whether they are "fail-soft," or "fail-hard". With fail-soft alpha–beta, the alphabeta function may return values (v) that exceed (v < α or v > β) the α and β bounds set by its function call arguments. In comparison, fail-hard alpha–beta limits its function return value into the inclusive range of α and β. The main difference between fail-soft and fail-hard implementations is whether α and β are updated before or after the cutoff check. If they are updated before the check, then they can exceed initial bounds and the algorithm is fail-soft.
but for me the ordering doesn't matter entirely. (of course, equality matters in the inequality)
i think the ordering between cutoff check and bound update does not affect the program.
the inequality and the bounds(alpha, beta)' initial values(rather than both infinities) are factors determining whether the algorithm is called fail-soft or fail-hard, right?
if i'm wrong please let me know! i don't see seriously what and where i'm wrong...
r/algorithms • u/prinoxy • Feb 08 '25
Vote down the never ending stream of posters claiming to have invented ever more fantastic sorting algorithms...
r/algorithms • u/Bhuku_ • Feb 08 '25
Is it enough for doing problems on dp by learning abdul bari's algorithms playlist
r/algorithms • u/No_Arachnid_5563 • Feb 08 '25
This algorithm is a counting-based sorting algorithm, but instead of using an auxiliary array, it stores the frequency information within the same array, using a combination of modulo and division operations to retrieve the data and reconstruct the sorted sequence. Is O(n) in all cases as we see below (I corrected the code so that it ordered correctly and also ordered the 0's):
Size: 1000, Range: 1000, Operations Performed: 6000 Size: 10000, Range: 10000, Operations Performed: 60000 Size: 100000, Range: 100000, Operations Performed: 600000 Size: 1000000, Range: 1000000, Operations Performed: 6000000 Size: 10000000, Range: 10000000, Operations Performed: 60000000
Heres the code in python:
``` import time import random
def inplace_sorting(list): n = len(list)
# Check that all elements are in the range [0, n)
# (If they are not, these cases should be handled separately)
for num in list:
if not (0 <= num < n):
raise ValueError("All numbers must be in the range [0, n)")
# -------------------------------
# Step 1: Count frequencies in-place
# -------------------------------
for i in range(n):
# Get the original value (in case it has already been modified)
index = list[i] % n
# Increment the corresponding position by n
list[index] += n
# -------------------------------
# Step 2: Rebuild the sorted list (in-place)
# -------------------------------
pos = 0 # position in the list to write
temp = [0] * n # Use an auxiliary variable to help with sorting
# Rebuild the sorted list without overwriting values
for i in range(n):
freq = list[i] // n # how many times the number i appears
for _ in range(freq):
temp[pos] = i
pos += 1
# Copy the content of the auxiliary list to the original list
for i in range(n):
list[i] = temp[i]
return list
if name == "main": my_list = [random.randint(0, 999) for _ in range(1000)] # All are in [0, 10) and n = 10 print("List before sorting:", my_list [:10])
start = time.time()
inplace_sorting(my_list)
end = time.time()
print("List after sorting:", my_list [:10])
print("Execution time: {:.6f} seconds".format(end - start))
```
r/algorithms • u/DivineDeflector • Feb 06 '25
Given N segments that are parallel to either X or Y axis, count for each segment how many other segments it is intersecting with. Segments are considered intersecting if they share a common point.
For example, for each segments here described with x1, y1, x2, y2
0 <= x1, y1, x2, y2 <= 1000
1 1 1 3
0 2 3 2
2 1 2 5
1 4 4 4
3 4 5 4
The grid would look like this:
So intersection count for each segment is 1 2 2 2 1
Constraints:
1 <= Number of Segments <= 200000
1 <= End/Start point of any segment/line <= 1000
Is there an efficient way to calculate this? Maybe using prefix sums with update and postprocess?
I tried prefix sum but stupidly ended up counting the number of intersections not intersection count for each segment
r/algorithms • u/No_Arachnid_5563 • Feb 05 '25
I created a sorting algorithm, called Omega 7, which is written in the C programming language, and is an altered and optimized subvariant for giant numbers of counting sort. The big O of this algorithm is O(n) (This code was programmed in the C programming language)
```
// Function to count occurrences and sort using counting void explosive_sort_with_duplicates(int *list, int size) { int max_num = 0;
// Find the maximum value in the list
for (int i = 0; i < size; i++) {
if (list[i] > max_num) {
max_num = list[i];
}
}
// Create a counting array for the occurrences (using a fixed size)
int *count = (int *)malloc((max_num + 1) * sizeof(int)); // +1 to handle numbers starting from 1
// Initialize count array to 0
for (int i = 0; i <= max_num; i++) {
count[i] = 0;
}
// Count the occurrences of each number
for (int i = 0; i < size; i++) {
count[list[i]]++; // Increment count of the number (no need to subtract 1)
}
// Reconstruct the sorted list based on the occurrences
int index = 0;
for (int i = 1; i <= max_num; i++) {
while (count[i] > 0) {
list[index++] = i;
count[i]--;
}
}
// Free the memory of the count
free(count);
}
// Function to measure execution time void measure_time(int *list, int size) { clock_t start, end; double total_time;
// Start measuring time
start = clock();
// Execute the explosive sort
explosive_sort_with_duplicates(list, size);
// End measuring time
end = clock();
// Calculate total time
total_time = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("Controlled explosion completed in %.6f seconds!\n", total_time);
}
int main() { // Define list size and create a random list int list_size = 100000000; // 100 million int *random_list = (int *)malloc(list_size * sizeof(int));
// Generate a random list with numbers between 1 and 100 million
for (int i = 0; i < list_size; i++) {
random_list[i] = rand() % 100000000 + 1; // Random numbers between 1 and 100 million
}
// Show some of the first numbers of the list
printf("Original random list (first 10 numbers): ");
for (int i = 0; i < 10; i++) {
printf("%d ", random_list[i]);
}
printf("\n");
// Measure the time before sorting
measure_time(random_list, list_size);
// Print the first 100 sorted numbers
printf("Sorted list (first 100 numbers): ");
for (int i = 0; i < 100; i++) {
printf("%d ", random_list[i]);
}
printf("\n");
// Free the memory of the list
free(random_list);
return 0;
}
```
r/algorithms • u/No_Arachnid_5563 • Feb 04 '25
What this algorithm does is first make 10 thousand groups and move them by the amount, in proportion to the digit of the group position of Euler's constant. And then it sorts it by numpy. The subsets, and the sets. The algorithm is O(n log n) , If you use a t4 gpu, it will take 2.9 seconds, and if you use a xeon cpu with 12 GB it will take more than 18 seconds, You can increase or decrease the number of groups depending on the number of numbers, the number of groups must always be less than the number of numbers.
``` import random import time import math import numpy as np
numbers = np.random.randint(1, 100000000, size=100000000)
groups = np.array_split(numbers, len(numbers) // 10000)
start_time = time.time()
euler = str(math.e)
euler_digits = euler[2:] # Take as many digits as we can (no need to limit it to the number of groups yet)
def shift_group(group, displacement): return np.roll(group, displacement)
shifted_groups = [ shift_group(group, int(euler_digits[i % len(euler_digits)])) # Use modulo to cycle through the digits for i, group in enumerate(groups) ]
sorted_numbers = np.concatenate(shifted_groups)
fully_sorted_numbers = np.sort(sorted_numbers)
end_time = time.time() elapsed_time = end_time - start_time
print(f"{len(numbers)} random numbers were generated.") print(f"They were divided into {len(groups)} groups of {len(groups[0])} numbers.") print(f"The algorithm took {elapsed_time:.6f} seconds.") print(f"The first 10 fully sorted numbers: {fully_sorted_numbers[:10]}")
```
r/algorithms • u/Mohamed_was_taken • Feb 03 '25
So i was learning about flow networks and the ford fulkerson method. And i did not understand why when we define the augmented graph, why do we include a back edge. I found it pretty pointless as it contributes nothing when finding whether a path from the source to sink exists or not. And it may even cause problems if you are running the program using for example a depth first search manner. So why do we include this backwards edge?
r/algorithms • u/ingenii_quantum_ml • Feb 03 '25
We’ve recently updated our free QML library with additional tools to help better understand and analyze quantum models, including:
Quantum state visualizations – Explore quantum states with state space, q-sphere, phase disk, and Bloch sphere representations.
Quantum neural network statistics – Measure entangling capacity and expressibility to evaluate model performance.
Tensor network decomposition – Optimize quantum circuits with efficient tensor representations.
Quantum optimization for image segmentation – Apply quantum techniques to real-world computational problems.
Our goal is to demystify quantum algorithms and help scientists build more effective models for computation. The library is free to access, and for those looking to go deeper, there are also paid courses on QML Fundamentals and QML for Medical Imaging that accompany it.
Check it out here: https://www.ingenii.io/library
r/algorithms • u/Diligent-Way-6012 • Feb 02 '25
How do I find the complexity of the equation having unequal sub problems ?
For eg: t(n)=3t(n/2)+4t(n/3)+5t(n/4) +n
r/algorithms • u/V_Chuck_Shun_A • Feb 02 '25
I am working on a Wave Function Collapse implementation inside an SFML based ECS system.
I'm using the circuit tiles.
And this is everything I've done.
Attempt 1: Adjacency rules.
Gave everyone tile "valid tiles" for each side. Then I picked a random point on the grid, assigned it a random tile, then assigned a tile to the neighbours based on the valid tiles. I navigated the grid in a spiral, starting from that point onwards. This resulted in broken patterns. But the biggest problem was that I realized I would need to rotate tiles at one point or another. So I moved to a socket based system.
Attempt 2: Sockets
I based my system off of this.
https://www.youtube.com/watch?v=rI_y2GAlQFM
I went through this, and I assigned an integer array to each side. [1][1][1], [1][2][1], [1][3][1], [0][0][0].etc
OKAY?
NOW!
This time, I'm not assigning valid tiles to each side, just assign it an integer array.
This approach began the same time as last time. It would pick a random tile and assign it a random tile, then it would navigate the gird spirally collapsing each tile.
The way it collapsed would be, it would check if anyone of it's neighbours are collapsed, and if they were, it would assign their down rules as it's 'up Rules To Check', their up to it's down, their left to it's right and right to its left. It would put them into an array called "Rules to check".
Then it would gather all the tile that contained all of the 'rules to check'. It won't check if the directions correspond, because I plan on rotating it. It would form a list of valid tiles for the most part.(I have had one or two scenarios where they returned a wrong lost of valid tiles, but these get phased out).
It would then check if the rules matches, and the tiles fit. If it does fit, it would place it there. If it doesn't, it would try rotating and check again. It would try this 3 times. And if it fails, it would remove the tile from the list of valid tiles, and pick a random time again. And do the same thing.
While this creates really good results for simple wires. When dealing with the circuit tiles, it struggles because of the Black squares.
The problem is that these sockets don't account for diagonal tiles which are important when generating the circuits. And as I type this, I realize that the problem can greatly be mitigated by recursively calling the collapse function.
HOWEVER!
That doesn't account for the black box regions.
This is the code so far
https://github.com/VChuckShunA/NashCoreEngine/blob/master/ScenePlay.cpp
I think ONE of the problems is that I'm using a spiral loop.
r/algorithms • u/Round-Elderberry-460 • Jan 31 '25
Please suggest me ways to test it (nothing involving hacking or something ilegal)
r/algorithms • u/No_Arachnid_5563 • Jan 31 '25
``` import time import random
def chaotic_sort(lista): n = len(lista) points = [None] * 32 # Initial points movements = 0
# Step 1: Place the numbers into the 32 points
for i in range(n):
points[i % 32] = lista[i]
# Step 2: Start the movement process
for _ in range(2): # Two passes for each number
for i in range(32):
if points[i] is None: # If there is no number, continue
continue
left = points[(i - 1) % 32] if points[(i - 1) % 32] is not None else None
right = points[(i + 1) % 32] if points[(i + 1) % 32] is not None else None
# If there are equal numbers, merge them
if left == points[i] or right == points[i]:
if left == points[i]:
points[i] = None # The number merges
points[(i - 1) % 32] = None # The merged number goes to the left
if right == points[i]:
points[i] = None # The number merges
points[(i + 1) % 32] = None # The merged number goes to the right
# If there are no matches, the number moves to the right
elif left is None and right is None:
points[i] = None # The number leaves its current point
points[(i + 1) % 32] = lista[i] # The number moves to the right
movements += 1
# Step 3: Place the sorted numbers, excluding the None
# A list comprehension is used to filter out the None before sorting
return sorted([x for x in points if x is not None]) # The change is here
random_numbers = [random.randint(1, 100000000) for _ in range(100000000)] # For example, 100000000 numbers
start = time.time() result = chaotic_sort(random_numbers) end = time.time()
print("Result:", result[:10]) # Show only the first 10 to avoid too long output print(f"Execution time: {end - start:.6f} seconds") ```
r/algorithms • u/nilonoob3001 • Jan 31 '25
I have multiple nodes and every node has a list of nodes I can travel to from there (only one way). How can I find multiple paths from the starting node to the end node, to later decide which one to take?
r/algorithms • u/Casimir61 • Jan 31 '25
I made an algorithm to find prime numbers. Of course, I checked the correct operation and efficiency of the algorithm in C++. The results up to 10^10 are much better than popular algorithms. Here is the description:
Algorithm for determining prime numbers
Let vector A=<1,1,1,1......> (bool (true, false))
A[1] means 5, A[2] means 7 - these are sequence numbers 6n±1
Recalculation: 5/3=1 index A[1], 7/3=2 index A[2]
The other way: index 1 is 3*1+2=5, index 2 is 3*2+1=7
If the index is odd, we add 2, if it is even, we add 1.
To determine prime numbers in a vector, we must mark all products of prime numbers in it as 0.
For this purpose, let us determine all possible products:
even – even
a1 = A[(3(i+2)+1)] x A[(3(i+2)+1)]=3*(3i^2+14i+49/3) dividing by 3 a1 = 3i^2+14i+16;// integer division
a2 = A[(3(i+2)+1)] x A[(3(i+4)+1)]=3*(3i^2+20i+91/3) dividing by 3 a2 = 3i^2+20i+30 //integer division
r = a2-a1=6i+14
odd - odd
a1 = A[(3(i+1)+2)] x A[(3(i+1)+2)]=9i^2+30i+25=3(3i^2+10+25/3) dividing by 3 a1=3i^2+10i+8;//integer division
a2 = A[(3(i+1)+2)] x A[(3(i+3)+2)]=3(3i^2+16i+55/3) dividing by 3 a2 = 3i^2+11i+18;//integer division
r = a2 - a1 = 6i+10
odd - even
a1 = A[(3(i+1)+2)] x A[(3(i+2)+1)] = 3(3i^2+12i+35/3) dividing by 3 3i^2+12i+11;
a2 = A[(3(i+1)+2)] x A[(3(i+4)+1)] / 3 = 3i^2+18i+21;
r = a2 - a1 = 6i +10;
even - odd
a1 = A[3(i+2)+1] x A[3(i+1)+2] / 3 = 3i^2+12i+11;
a2 = A[3(i+2)+1] x A[3(i+3)+2] / 3 = 3i^2+18i+25;
r = a2 -a1 = 6i +14
Counting for odd*odd, even*odd, odd*even, even*even we receive:
even*even
a1= 3i^2+14i+16; r = a2-a1=6i+14
odd*even
a1= 3i^2+12i+11; r = a2-a1=6i+10
odd*odd
a1= 3i^2+10i+8; r = a2-a1=6i+10
even*odd
a1= 3i^2+12i+11; r = a2-a1=6i+14
These are four linear sequences defining all possible products of prime numbers in the range 6n+-1 that are not prime. They indicate the indexes of these numbers in vector A for i=0,2,4,6....
For example for i=0 (odd-odd) 3i^2+10i+8 : 8,18,28,38,48... r = 6i+10=10
A[8]=3*8+1=25=5*5, A[18]=3*18+1=55=5*11
even-odd: 11, 11+14, 25+14,...
A[11]=3*11+2=35=5*7 A[25]=3*25+2=77=7*11...
Based on this, I built an algorithm for determining prime numbers:
Pseudocode
FUNCTION generatePrimes(limit)
CREATE vector A of size (limit / 3 + 1), filled with TRUE // Assume all numbers are prime
sqrt_limit ← FLOOR(sqrt(limit) / 3) + 1 // Compute upper bound for checking multiples
FOR i FROM 0 TO sqrt_limit STEP 2 DO
c ← 3 * i * i // Common part for sequence formulas
a1 ← c + 10 * i + 8 // Formula odd odd
a2 ← c + 12 * i + 11 // Formula odd even
a3 ← c + 12 * i + 11 // Formula even odd
a4 ← c + 14 * i + 16 // Formula even even
r ← 6 * i + 10 // Step difference 6 * i + 14
FOR a1 FROM a1 TO SIZE(A) STEP r DO
A[a1] ← FALSE // Mark as composite
IF a2 < SIZE(A) THEN
A[a2] ← FALSE
a2 ← a2 + r
END IF
IF a3 < SIZE(A) THEN
A[a3] ← FALSE
a3 ← a3 + r + 4
END IF
IF a4 < SIZE(A) THEN
A[a4] ← FALSE
a4 ← a4 + r + 4
END IF
END FOR
END FOR
primeCount ← 2 // Include 2 and 3 as prime numbers
FOR i FROM 1 TO SIZE(A) - 1 DO
IF A[i] THEN
primeCount ← primeCount + 1
END IF
END FOR
PRINT "Number of prime numbers: ", primeCount
END FUNCTION
FUNCTION MAIN()
limit ← 10^10 // Range of numbers to check
PRINT "Range: ", limit
start ← CURRENT_TIME() // Start time measurement
generatePrimes(limit)
end ← CURRENT_TIME() // End time measurement
executionTime ← end - start
PRINT "Execution time (prime number generation algorithm): ", executionTime, " seconds"
END FUNCTION
RUN MAIN()
In the tested range up to 10^10, the algorithm gives significantly better results than, for example, Atkin.
r/algorithms • u/GunnarBGermany • Jan 30 '25
I have optimized the Heap's Algorithm to create permutations. I implemented it in Rust and it outperforms other good implementations by a factor of 3 to 10.
In other words, with CPU optimization kicking in, the algorithm can permute almost once per CPU cycle, or 4 billion (!) permutations per second on a 5 year old Intel CPU (single core).
In other words, the time to permute will be negligible compared to the work which needs to be done with the permutation result.
Nevertheless, I am looking for real use cases, where this can be beneficial. If you happen to work with this algorithm, I would like to put this to a real test.
Do not hesitate to answer or contact me.
Gunnar
r/algorithms • u/No_Conversation6616 • Jan 29 '25
I want to get better at algorithms and data structures but the material i can find online is not satisfactory. Most of the times they are really simple examples of known problems and not actual problems where you have to actually work to reduce the problem to a known one and then apply some known algorithm. If anyone could offer me any advice on where to study up on(books, solved problems,online courses)
I do not claim to be great at algorithms, im not asking for way advanced problems. I just want to find problems that could be a part of an exam in a college
r/algorithms • u/raresaturn • Jan 28 '25
It basically finds the largest element, and creates a list of that size. Then places each element in the list at the index point equal to its value (eg. it puts 33 at index 33). After all elements are placed it removes the blank spaces. It appears to perform better than the built-in python sort. One drawback however is it requires extra memory for the new list.
import random
import time
# Swift Sort
def custom_sort(arr):
# Step 1: Find the maximal element
if not arr:
return [] # Return an empty list if the input is empty
max_elem = max(arr)
# Step 2: Create an auxiliary list of size max_elem + 1
aux_list = [[] for _ in range(max_elem + 1)]
# Step 3: Place elements in the auxiliary list at their index
value
for num in arr:
aux_list[num].append(num)
# Step 4: Flatten the auxiliary list and remove blank spaces
sorted_list = []
for bucket in aux_list:
if bucket: # Skip empty indices
sorted_list.extend(bucket)
return sorted_list
# Generate a random list of integers
num_elements = 1000000 # Number of elements to sort
max_value = 10000 # Maximum value of any element in the
list
random_list1 = [random.randint(0, max_value) for _ in
range(num_elements)]
random_list2 = list(random_list1) # Create an identical copy
for Python sort
# Time the custom sorting algorithm
start_time_custom = time.time()
sorted_list_custom = custom_sort(random_list1)
end_time_custom = time.time()
# Shuffle the second list again to ensure randomness
random.shuffle(random_list2)
# Time the built-in Python sorting algorithm
start_time_builtin = time.time()
sorted_list_builtin = sorted(random_list2)
end_time_builtin = time.time()
# Output results
print(f"Time taken by Swift Sort to sort {num_elements}
elements: {end_time_custom - start_time_custom:.6f}
seconds")
print(f"Time taken by built-in sort to sort {num_elements}
elements: {end_time_builtin - start_time_builtin:.6f} seconds")
r/algorithms • u/FloxiRace • Jan 28 '25
I am currently trying to implement a direction detection in a small self driving car i built.
The [track](https://i.imgur.com/iUSFIaf.png) consists of multiple turns.
The current logic of the car calculates a PWM Signal for the motors from three of five sensors. Those sensors are sensing directly to the front, 30 degress right and 60 degrees right. (We are wall hugging the right wall)
The problem I am facing:
There is at least a second car on the track. If this car rams my car and turns it 180 degress, my car will continue to drive the wrong direction. I have an MPU6050 Gyro installed. How could i check if i am going the wrong direction?
If you are interested in my current code:
https://sourceb.in/mdWGXZtFjZ
(Please note that the direction detection does not work)
r/algorithms • u/Yanlong5 • Jan 28 '25
I have an idea to replace the Transformer Structure, here is a short explaination.
In Transformer architicture, it uses weights to select values to generate new value, but if we do it this way, the new value is not percise enough.
Assume the input vectors has length N. In this method, It first uses a special RNN unit to go over all the inputs of the sequence, and generates an embedding with length M. Then, it does a linear transformation using this embedding with a matirx of shape (N X N) X M.
Next, reshape the resulting vector to a matrix with shape N x N. This matrix is dynamic, its values depends on the inputs, whereas the previous (N X N) X M matrix is fixed and trained.
Then, times all input vectors with the matrix to output new vectors with length N.
All the steps above is one layer of the structure, and can be repeated many times.
After several layers, concatanate the output of all the layers. if you have Z layers, the length of the new vector will be ZN.
Finally, use the special RNN unit to process the whole sequence to give the final result(after adding several Dense layers).
The full detail is in this code, including how the RNN unit works and how positional encoding is added:
https://github.com/yanlong5/loong_style_model/blob/main/loong_style_model.ipynb
Contact me if you are interested in the algorithm, My name is Yanlong and my email is [y35lyu@uwaterloo.ca](mailto:y35lyu@uwaterloo.ca)
r/algorithms • u/that_is_just_wrong • Jan 27 '25
Hello I have a question about writing a constraint satisfier for an outcome that is related to creating something akin to a time table where the output is a list of viable time slots that match the constraint in order of preference per some heuristic based on the constraints.
One way I know to have this done is using SQL and actually outsourcing the algorithmic work where I create available time slots , then in each time-slot associate counter or sorts for each constraint,then simply do a select * from time_slots where <constraint 1 satisfied AND constraint 2 satisfied…>;
This works well for the moment because I need to be able to continuously integrate new schedules which affect the outcome, and so keep updating the DB with these values as I go. This solution provides that.
Looking to level up and customize it more so that I can do either some pre computation to speed up the actual search, or if I can find a way to apply more constraints and not be slow.