Optimized Collatz Conjecture tester.

Collatz Conjecture tester

This optimized Collatz Conjecture tester can test the provided numbers for how many iterations they need before they reach the number 1. The path is not printed, only statistics: the number of 3*n+1 ("mul3") and n/2 ("div2") operations, and total. As a progress indicator prints the current length of the number in bytes (every 25000 iterations).

If you're lucky to find a number that proves that Collatz Conjecture is false (or a bug in the program), then the program will hang in an infinite loop.

  • Note: Doesn't work with negative numbers.

Building

  1. make all
    default build
  2. make profile PROF_ARGS="--ones 1000000"
    build with the profile-guided optimizations using GCC (add CLANG=1 when using Clang)
  • make check for a simple build check.
  • Compile-time option NBITS, greatly affects performance, should be the number of bits in the machine register. The default is 64 for 64-bit machines (also needs the __int64 type supported by the compiler), otherwise 32.

Usage

collatz_test [--lut 1..26] [mode] {num|file}

Options

--lut N builds a lookup table to speed up the process by a factor of N (default 20). LUT consumes 2^n * 3 * NBITS/8 bytes of memory. The LUT depth is also limited to 5 * NBITS/8.

  • Doesn't affect performance in the latest version with dynamic expansion of LUT values.

Modes

--num read decimal number from command line (default)
--file load specified file as a little endian number
--ones test 2^n-1

Example

$ ./collatz_test 989345275647
mul3 = 506, div2 = 842, total = 1348
$ ./collatz_test 0xffffffff
mul3 = 162, div2 = 289, total = 451
$ ./collatz_test --ones 1000000
lut: 0.016s
bytes: 198128
bytes: 145760
bytes: 94000
bytes: 41896
mul3 = 4805005, div2 = 8615753, total = 13420758
time: 1.155s
$ head -c100000 /dev/urandom > random.bin
$ ./collatz_test --file random.bin
lut: 0.016s
bytes: 47936
mul3 = 1923602, div2 = 3848837, total = 5772439
time: 0.213s
Owner
Ilya Kurdyukov
Optimization, porting, SIMD, image processing.
Ilya Kurdyukov
Similar Resources

OpenBLAS is an optimized BLAS library based on GotoBLAS2 1.13 BSD version.

OpenBLAS Travis CI: AppVeyor: Drone CI: Introduction OpenBLAS is an optimized BLAS (Basic Linear Algebra Subprograms) library based on GotoBLAS2 1.13

Nov 23, 2022

H2O - the optimized HTTP/1, HTTP/2, HTTP/3 server

H2O - an optimized HTTP server with support for HTTP/1.x, HTTP/2 and HTTP/3 (experimental) Copyright (c) 2014-2019 DeNA Co., Ltd., Kazuho Oku, Tatsuhi

Nov 27, 2022

Heavily optimized zlib compression algorithm

Optimized version of longest_match for zlib Summary Fast zlib longest_match function. Produces slightly smaller compressed files for significantly fas

Oct 29, 2022

An optimized C library for math, parallel processing and data movement

PAL: The Parallel Architectures Library The Parallel Architectures Library (PAL) is a compact C library with optimized routines for math, synchronizat

Nov 22, 2022

📽 Highly Optimized Graphics Math (glm) for C

🎥 OpenGL Mathematics (glm) for C Documentation Almost all functions (inline versions) and parameters are documented inside the corresponding headers.

Nov 20, 2022

📽 Highly Optimized Graphics Math (glm) for C

🎥 OpenGL Mathematics (glm) for C Documentation Almost all functions (inline versions) and parameters are documented inside the corresponding headers.

Nov 27, 2022

RemixDB: A read- and write-optimized concurrent KV store. Fast point and range queries. Extremely low write-amplification.

REMIX and RemixDB The REMIX data structure was introduced in paper "REMIX: Efficient Range Query for LSM-trees", FAST'21. This repository maintains a

Nov 1, 2022

A command-line tool for converting heightmaps in GeoTIFF format into tiled optimized meshes.

A command-line tool for converting heightmaps in GeoTIFF format into tiled optimized meshes.

TIN Terrain TIN Terrain is a command-line tool for converting heightmaps presented in GeoTIFF format into tiled optimized meshes (Triangulated Irregul

Nov 16, 2022

Kreon is a key-value store library optimized for flash-based storage

Kreon is a key-value store library optimized for flash-based storage

Kreon is a key-value store library optimized for flash-based storage, where CPU overhead and I/O amplification are more significant bottlenecks compared to I/O randomness.

Jul 14, 2022

C++ wrappers for SIMD intrinsics and parallelized, optimized mathematical functions (SSE, AVX, NEON, AVX512)

C++ wrappers for SIMD intrinsics and parallelized, optimized mathematical functions (SSE, AVX, NEON, AVX512)

Nov 21, 2022

Optimized JSON in C

Optimized JSON in C Description Optimized JSON in C (OjC), as the name implies, was written to provide optimized JSON handling. It is derived from the

Nov 12, 2022

WasmEdge Runtime is a high-performance, extensible, and hardware optimized WebAssembly Virtual Machine for automotive, cloud, AI, and blockchain applications.

WasmEdge Runtime is a high-performance, extensible, and hardware optimized WebAssembly Virtual Machine for automotive, cloud, AI, and blockchain applications.

Nov 23, 2022

📽 Highly optimized 2D|3D math library, also known as OpenGL Mathematics (glm) for `C

📽 Highly optimized 2D|3D math library, also known as OpenGL Mathematics (glm) for `C

Highly optimized 2D|3D math library, also known as OpenGL Mathematics (glm) for `C`. cglm provides lot of utils to help math operations to be fast and quick to write. It is community friendly, feel free to bring any issues, bugs you faced.

Nov 30, 2022

Optimized, fast and unsafe Uniswap sniping bot for buying new listings.

Optimized, fast and unsafe Uniswap sniping bot for buying new listings.

Optimized, fast and unsafe Uniswap sniping bot for buying new listings. Table of content How does it work? Pregeneration Used libraries Project struct

Nov 12, 2022

percepnet implemented using Keras, still need to be optimized and tuned.

PercepNet (Still need to be tuned) Unofficial implementation of PercepNet : A Perceptually-Motivated Approach for Low-Complexity, Real-Time Enhanceme

Nov 17, 2022

This repo is for competitive coders. In the readme file you will get the list of questions. You can contribute by adding your solutions or by providing the optimized solutions which are answered already.

This repo is for competitive coders. In the readme file you will get the list of questions. You can contribute by adding your solutions or by providing the optimized solutions which are answered already.

Hello, Problem Solvers !!! 💥 What it's about? 👩‍💻 This repository is for Competitive Coders to get started with Open-source. 📃 We have curated a l

Oct 22, 2022

An optimized neural network operator library for chips base on Xuantie CPU.

简介 CSI-NN2 是 T-HEAD 提供的一组针对无剑 SoC 平台的神经网络库 API。抽象了各种常用的网络层的接口,并且提供一系列已优化的二进制库。 CSI-NN2 的特性: 开源 c 代码版本的参考实现。 提供玄铁 CPU 的汇编优化实现。

Nov 20, 2022

Optimized implementations of the Number Theoretic Transform (NTT) algorithm for the ring R/(X^N + 1) where N=2^m.

optimized-number-theoretic-transform-implementations This sample code package is an implementation of the Number Theoretic Transform (NTT) algorithm f

Nov 14, 2022

An optimized version of the KGloVe code (global embeddings for Knowledge Graphs)

Optimized Implementation of the KGloVe algorithm This repository contains an optimized implementation of KGloVe, which was proposed in Cochez M., Rist

Feb 25, 2022
A tester for game controller written in C, using SDL2.

SDL2 Controller Tester This little application has been made while I was attending a tutorial to make games in C using SDL2. Since my purpose will be

Jul 31, 2022
A tester for the ft_printf 42 project.

ft_printf tester A tester for 42's ft_printf project. Updated for the new specification (2021 2nd semester) It runs a series of tests against ft_print

Nov 17, 2022
Simple ft_printf (2021) tester for the mandatory requirements
Simple ft_printf (2021) tester for the mandatory requirements

Welcome to the MK_Test ?? Simple ft_printf (2021) tester for the mandatory requirements Disclaimers This tester only checks the MANDATORY requirements

Jul 22, 2022
The ultimate battery tester with ESR measurement and discharge graph. Based on an Arduino Nano and a 1602 LCD.
The ultimate battery tester with ESR measurement and discharge graph. Based on an Arduino Nano and a 1602 LCD.

Ultimate-Battery-Tester Version 1.0.0 Features Measures the ESR (equivalent series resistance) of the battery. This is an idicator of the health of th

Nov 1, 2022
A push_swap tester
A push_swap tester

complexity Usage ./complexity [-hs] [-p file ] numbers iterations [ goal ] [ checker ] L'exécutable push_swap est cherché par défaut dans le répertoir

Oct 28, 2022
📝 One of the difficult unit tester for ft_containers project
📝 One of the difficult unit tester for ft_containers project

ft_containers-unit-test About ft containers unit test is a complete testing for project of school 21/ecole 42 and allowing you test your containers: V

Nov 21, 2022
A Tester for the Libft 42 project based off Tripouille

libfttester A Tester for the Libft 42 project This Tester was made by NotJustJoe, using Tripouille Leaks checker and kind of inspired off his work (ht

May 20, 2022
Dperf is a 10M HTTP CPS Load Tester.

Dperf is a 10M HTTP CPS Load Tester Dperf is a high performance network load tester. Thanks to DPDK and highly optimized network protocol stack, it ca

Nov 22, 2022
Bolt is a C++ template library optimized for GPUs. Bolt provides high-performance library implementations for common algorithms such as scan, reduce, transform, and sort.

Bolt is a C++ template library optimized for heterogeneous computing. Bolt is designed to provide high-performance library implementations for common

Nov 14, 2022
Optimized primitives for collective multi-GPU communication

NCCL Optimized primitives for inter-GPU communication. Introduction NCCL (pronounced "Nickel") is a stand-alone library of standard communication rout

Nov 24, 2022