Prime Number Projects in C#/C++/Python

Overview

Primes | A Software Drag Race

Note: You're currently looking at the community contribution branch of this repo, which is now the default. The original branch can be found here.

Source code to Dave's Garage video benchmarking the same prime number sieve in Python, C#, and C++.

Software Drag Racing | Dave's Garage

Build status

example workflow

Community contributions

Community contributions, fixes and improvements are accepted on this branch. If you want to add your own solution, please read CONTRIBUTING.md.

Running all benchmarks

All benchmarks (solutions) in this repository can be built and run with one Makefile. This is described in BENCHMARK.md.

Viewing results

The PrimeView web application can be used to view, filter and sort results generated by Dave's benchmark machine. It is our intention to add results of other systems in the future. Note that any feedback, suggestions, PRs concerning PrimeView need to be made on the application's own repository.

Comments
  • Add Kotlin Solution

    Add Kotlin Solution

    Description

    Add a fast and an idiomatic Kotlin Solution. Both solutions are roughly based around the Java solution. The fast solution focuses on producing clean bytecode while the idiomatic solution focuses on writing more real-world readable code.

    Contributing requirements

    • [x] I read the contribution guidelines in CONTRIBUTING.md.
    • [x] I placed my solution in the correct solution folder.
    • [x] I added a README.md with the right badge(s).
    • [x] I added a Dockerfile that builds and runs my solution.
    • [x] I selected drag-race as the target branch.
    • [x] All code herein is licensed compatible with BSD-3.
    opened by Theaninova 59
  • Scala tail recursive solution

    Scala tail recursive solution

    Description

    Scala solution to the Prime Sieve Drag Race.

    • Apparently Scala solution_1 is broken*, so this provides the first working implementation on Scala
      • This solution also ~4X faster than solution_1, although comparing to an incorrect solution is fairly pointless
      • Around 4000 passes on my machine (2018 ultrabook, WSL 2 on Win10)
    • Used solution_1 as a base for Docker and build files
    • Uses tail recursion for the loops (compiled to while loops by the Scala compiler)
    • Uses sentinel in the bit (Boolean array) to avoid some out-of-bounds checks
    • EDIT: Also adds trivial fix to solution_1 (see discussion)

    Solution_1 output*:

    2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, 67, 71, 73, 77, 79, 83, 85, 89, 91, 95, 97, 
    rom1dep;2059635;5.0;1;algorithm=base,faithful=yes
    

    Contributing requirements

    • [X] I read the contribution guidelines in CONTRIBUTING.md.
    • [X] I placed my solution in the correct solution folder.
    • [X] I added a README.md with the right badge(s).
    • [X] I added a Dockerfile that builds and runs my solution.
    • [X] I selected drag-race as the target branch.
    • [X] All code herein is licensed compatible with BSD-3.
    opened by scilari 41
  • Add much faster Nim version as solution_3

    Add much faster Nim version as solution_3

    Description

    Add a Nim version that corrects many of the problems with "solution_1" and "solution_2" including more efficient use of CPU caches and "Extreme Loop Unrolling", which is a technique similar to the "striping" technique used by the fastest Rust implementation, but refined yet further.

    Contributing requirements

    • [x] I read the contribution guidelines in CONTRIBUTING.md.
    • [x] I placed my solution in the correct solution folder.
    • [x] I added a README.md with the right badge(s).
    • [x] I added a Dockerfile that builds and runs my solution.
    • [x] I selected drag-race as the target branch.
    • [x] All code herein is licensed compatible with BSD-3.
    opened by GordonBGood 37
  • Improved speed ~4-5x for PHP

    Improved speed ~4-5x for PHP

    No longer uses class methods for basic operations. Leaned the loop logic. Uses factor * factor. Uses SplFixedArray rather than normal array, they use less memory and are faster. Enable PHP JIT.

    Description

    @DennisdeBest Would you like to comment?

    Contributing requirements

    • [x] I read the contribution guidelines in CONTRIBUTING.md.
    • [x] I placed my solution in the correct solution folder.
    • [x] I added a README.md with the right badge(s).
    • [x] I added a Dockerfile that builds and runs my solution.
    • [x] I selected drag-race as the target branch.
    • [x] All code herein is licensed compatible with BSD-3.
    opened by xeridea 30
  • Dockerlint part 1

    Dockerlint part 1

    The following programming languages and their solutions have been checked and fixed based on Dockerlint: PrimeAda PrimeAmd64 PrimeAssembly PrimeAssemblyScript PrimeAWK

    ~~Note that somehow, i was unable to build PrimAmd64 for example. The dockerfiles look right in my eyes and even with some testing i can see the files. I assume it's just me and i only added versioning on them.

    #9 [5/6] RUN ls -al
    #9 sha256:3daebede1a2c80e94db8b4f17304c512b69bc8e5e1e381de464b26d0d6d380d7
    #9 0.325 total 104
    #9 0.325 drwxr-xr-x    1 root     root          4096 Sep  8 19:17 .
    #9 0.325 drwxr-xr-x    1 root     root          4096 Sep  8 19:17 ..
    #9 0.325 -rwxr-xr-x    1 root     root           705 Sep  7 20:11 build.sh
    #9 0.325 -rwxr-xr-x    1 root     root         13407 Sep  7 20:11 primes_ff_bitbtr.asm
    #9 0.325 -rwxr-xr-x    1 root     root         14217 Sep  7 20:11 primes_ff_bitshift.asm
    #9 0.325 -rwxr-xr-x    1 root     root         12315 Sep  7 20:11 primes_ff_byte.asm
    #9 0.325 -rwxr-xr-x    1 root     root         11023 Sep  7 20:11 primes_uff_bitbtr.asm
    #9 0.325 -rwxr-xr-x    1 root     root         10989 Sep  7 20:11 primes_uff_bitshift.asm
    #9 0.325 -rwxr-xr-x    1 root     root          9189 Sep  7 20:11 primes_uff_byte.asm
    #9 0.325 -rwxr-xr-x    1 root     root           160 Sep  7 20:11 run.sh
    #9 DONE 0.3s
    
    #10 [6/6] RUN ./build.sh
    #10 sha256:24f3007ef2678ffd943c784cb2ca58d2f1a23b4e988c223c540aa612a9ce1576
    #10 0.506 /bin/sh: ./build.sh: not found
    #10 ERROR: executor failed running [/bin/sh -c ./build.sh]: exit code: 127
    ```~~
    
    Feel free to review and give feedback, next i'll do another 5 after primeawk :)
    
    I did test in docker playground and it just works from my fork. So i assume it's just a me thing :P 
    opened by Macleykun 29
  • JavaScript (Node.js) implementation

    JavaScript (Node.js) implementation

    Created a Nodejs implementation, primarily copied from the C# version.

    JS supports bitwise operations for integers, which vastly improves performance compared to using parseInt(index / 2). (I'm pleasantly surprised that it performs significantly better than the Python implementation.)

    NOTE: To run using Node.js: run node PrimeJS.js

    type:stl-faithful language:JS 
    opened by JL102 28
  • Setup CI for this project

    Setup CI for this project

    Hello,

    It would be nice to set up some CI to run these implementations in a controlled environment periodically. We're getting benchmarks from different machines, and it is hard to keep track of all the numbers for all the different implementations. We need one source of truth.

    automation 
    opened by marghidanu 27
  •  Adding a faithful implementation of the C# solution

    Adding a faithful implementation of the C# solution

    On my own box, C++ measures:

    Passes: 8665, Time: 5.000000, Avg: 0.000577, Limit: 1000000, Count1: 78498, Count2: 78498, Valid: 1
    
    davepl;8665;5.000000;1
    

    This builds on @EgorBo's PR in https://github.com/davepl/Primes/pull/4 and gets the C# version to:

    Passes: 7883, Time: 5.0001565, Avg: 0.0006342961436001523, Limit: 1000000, Count: 78498, Valid: True
    
    tannergooding;7883;5.0001565;1
    

    The key points are to elide bounds checks and more closely mirror what C++ in terms of types and code used to make it a more fair comparison. C# inherently does things C++ doesn't, like bounds checks. If the version to version comparisons were to be equally safe (with C++ using things like std::array and doing bounds checking before accesses, eliding where it is statically determined to be "safe"), then C++ wouldn't have such a "clear lead" 😄

    type:stl-faithful language:C# 
    opened by tannergooding 27
  • Another improvement to dart solution_1

    Another improvement to dart solution_1

    Description

    I was able to improve the times even further on dart solution_1 by initializing the bits list to half the sieve size, and adjusting the indexing accordingly.

    Contributing requirements

    • [x] I read the contribution guidelines in CONTRIBUTING.md.
    • [x] I placed my solution in the correct solution folder.
    • [x] I added a README.md with the right badge(s).
    • [x] I added a Dockerfile that builds and runs my solution.
    • [x] I selected drag-race as the target branch.
    • [x] All code herein is licensed compatible with BSD-3.
    opened by mmcdon20 26
  • Would anyone like to Admin this project?  Someone knowledgeable in the ways of Github?

    Would anyone like to Admin this project? Someone knowledgeable in the ways of Github?

    If so, please chime in and volunteer! I wasn't really anticipating the amount of interest and I've got 30+ pull requests and I'm swamped just doing the benchmarking and making the videos, but if someone would like to take over this project and maintain the source to the Drag Racing series, I'd love that!

    My goal is to be able to keep the original branch with only a very few changes. I have a few checking queued up of my own, which I will check in, and then leave the main branch alone. I want as few changes in the main branch as possible to keep the tests similar from one episode to the next, but we can party alongside it for sure!

    But if folks want to add side-projects for ports to other languages (I know folks have already submitted D, Rust, Java, and others!) the can go in folders alongside, like PrimeJava.

    If you're interested, please let me know! Ideally with a one or two snippet of your experience with GitHub!

    Thanks! Dave

    opened by davepl 26
  • TeX solution

    TeX solution

    Benchmarking uses pdftex for its timing facilities

    Description

    Contributing requirements

    • [x] I read the contribution guidelines in CONTRIBUTING.md.
    • [x] I placed my solution in the correct solution folder.
    • [x] I added a README.md with the right badge(s).
    • [x] I added a Dockerfile that builds and runs my solution.
    • [x] I selected drag-race as the target branch.
    • [x] All code herein is licensed compatible with BSD-3.
    opened by jfbu 25
  • Improve C# perf from 300 to 1305 passes per second

    Improve C# perf from 300 to 1305 passes per second

    Description

    Contributing requirements

    • [x] I read the contribution guidelines in CONTRIBUTING.md.
    • [x] I placed my solution in the correct solution folder.
    • [x] I added a README.md with the right badge(s).
    • [x] I added a Dockerfile that builds and runs my solution.
    • [x] I selected drag-race as the target branch.
    • [x] All code herein is licensed compatible with BSD-3.
    opened by davepl 15
  • Added arch files

    Added arch files

    Running the benchmark under my M1 machine yielded quite a few errors on the following solutions:

    error: [PrimeCSharp][solution_2] Failed building solution!
    error: [PrimeDart][solution_1] Failed building solution!
    error: [PrimeHaskell][solution_1] Failed building solution!
    error: [PrimeJulia][solution_1] Failed building solution!
    error: [PrimeJulia][solution_2] Failed building solution!
    error: [PrimeSwift][solution_1] Failed building solution!
    error: [PrimeZig][solution_1] Failed building solution! 
    error: [PrimeZig][solution_3] Failed building solution!
    error: [PrimeJava][solution_2] Failed building solution!
    error: [PrimeFortran][solution_2] Failed building solution!
    
    warn: [PrimeLua][solution_2] Exited with abnormal code: 1. Results might be partial... (can be fixed)
    warn: [PrimePascal][solution_1] Exited with abnormal code: 217. Results might be partial...
    warn: [PrimeWren][solution_1] Exited with abnormal code: 255. Results might be partial...
    

    I've added the arch-amd64 flag for these since they fail to build/run under arm64.

    opened by marghidanu 13
Owner
Plummer's Software LLC
Handles billing
Plummer's Software LLC
Python Inference Script is a Python package that enables developers to author machine learning workflows in Python and deploy without Python.

Python Inference Script(PyIS) Python Inference Script is a Python package that enables developers to author machine learning workflows in Python and d

Microsoft 13 Nov 4, 2022
Using Visual Studio C++ to read IP addresses and comport number (Serial number) on Windows platform

Using Visual Studio C++ to read IP addresses on Windows platform

zhuhuijin 0 Feb 2, 2022
Kaprekar constant, number 6174, number 495.

Kaprekar Constant Demos Kaprekar constant, number 6174, number 495. This repository contains 1 Visual Studio solution, which managing 2 Visual Studio

MatrixLife 1 Dec 25, 2021
The music of Fibonacci and prime numbers

fibprimes "Main" branch contains source code and generated MIDI file. "MP3" branch contains the MP3 file converted from the MIDI file. General Each ch

null 25 Feb 4, 2022
🔥 A number of Flutter projects that cover slightly more complex topics.

Check out the YouTube videos to see the indepth process of each project! Reactive Grid https://youtu.be/OEtt_8_FU0s Fancy Full Screen Animation https:

Philip Vu 26 Oct 26, 2022
Sharpmake is an open-source C#-based solution for generating project definition files, such as Visual Studio projects and solutions, GNU makefiles, Xcode projects, etc.

Sharpmake Introduction Sharpmake is a generator for Visual Studio projects and solutions. It is similar to CMake and Premake, but it is designed for s

Ubisoft 777 Nov 25, 2022
BLLIP reranking parser (also known as Charniak-Johnson parser, Charniak parser, Brown reranking parser) See http://pypi.python.org/pypi/bllipparser/ for Python module.

BLLIP Reranking Parser Copyright Mark Johnson, Eugene Charniak, 24th November 2005 --- August 2006 We request acknowledgement in any publications that

Brown Laboratory for Linguistic Information Processing 214 Oct 22, 2022
A Binary Clock. Written 3 different ways. C and SDL, Python and PyGame, Python and PyGame Zero.

Super Clock A Binary Clock. Written 3 different ways. Python with PyGame Zero, Python with PyGame and C with SDL2. Time is displayed in 3 groups of 8

null 3 Dec 8, 2021
LibTomMath is a free open source portable number theoretic multiple-precision integer library written entirely in C.

libtommath This is the git repository for LibTomMath, a free open source portable number theoretic multiple-precision integer (MPI) library written en

libtom 540 Nov 23, 2022
Universal Number Arithmetic

Universal: a header-only C++ template library for universal number arithmetic The goal of the Universal Numbers Library is to offer applications alter

Stillwater Supercomputing, Inc. 292 Nov 15, 2022
A collection of single-file C libraries. (generic containers, random number generation, argument parsing and other functionalities)

cauldron A collection of single-file C libraries and tools with the goal to be portable and modifiable. Libraries library description arena-allocator.

Camel Coder 38 Oct 26, 2022
Number recognition with MNIST on Raspberry Pi Pico + TensorFlow Lite for Microcontrollers

About Number recognition with MNIST on Raspberry Pi Pico + TensorFlow Lite for Microcontrollers Device Raspberry Pi Pico LCDディスプレイ 2.8"240x320 SPI TFT

iwatake 50 Oct 9, 2022
Terminal calculator made for programmers working with multiple number representations, sizes, and overall close to the bits

Programmer calculator The programmer calculator is a simple terminal tool designed to give maximum efficiency and flexibility to the programmer workin

romes 174 Nov 22, 2022
A fast phone number lib for Ruby (binds to Google's C++ libphonenumber)

MiniPhone A Ruby gem which plugs directly into Google's native C++ libphonenumber for extremely fast and robust phone number parsing, validation, and

Ian Ker-Seymer 147 Oct 30, 2022
Simulation code for the specific PDP-10 serial number 32 at the Stanford A. I. Lab in 1974 as a solo processor with all the I/O devices simulated as on the PDP-10. Omit the co-processor PDP-6 sn16.

KA10 sn32 Synopsis This repository contains software and documentation for running the unique PDP-10 KA serial number 32 that was at Stanford in July

Saildart Archive 4 Aug 7, 2021
An embedded system for displaying current number of followers on bilibili. A reproduction of eInkBoard v1. 一个能显示哔哩哔哩账号实时粉丝数的嵌入式系统,eInkBoard v1 的复刻版。

eInkBoard v2 An embedded system for displaying current number of followers on bilibili. A reproduction of eInkBoard v1 (this page is in Chinese). 一个能显

Karbon Chen 4 Dec 6, 2021
FractalCrypt - Free cryptoarchiver permitting any number of hidden volumes for deniable encryption

FractalCrypt - Free cryptoarchiver permitting any number of hidden volumes for deniable encryption

Ivan Serov 358 Nov 23, 2022
Trident provides an easy way to pass the output of one command to any number of targets.

Trident: The multiple-pipe system Trident provides an easy way to pipe the output of one command to not just one but many targets. These targets can b

Matthias Gessinger 36 Nov 23, 2021
A fast character conversion and transliteration library based on the scheme defined for Japan National Tax Agency (国税庁) 's corporate number (法人番号) system.

jntajis-python Documentation: https://jntajis-python.readthedocs.io/ What's JNTAJIS-python? JNTAJIS-python is a transliteration library, specifically

Open Collector, Inc. 15 Nov 12, 2022