# Find position of bit in byte with one bit set

Gegeben ist ein Byte mit einem gesetzten Bit: i.e. 1,2,4,8,16,32,64,128

Die Position des gesetzten Bits soll gefunden werden:
i.e. Byte = 1 enstpricht Position 1
i.e. Byte = 64 entspricht Position 7

… ended up with deBruijn (without knowing then …)

``````
package main

/*
int pos(int a){
int p = (a & 3) | ((a >> 1) & 6) | ((a >> 2) & 5) | ((a >> 3) & 4) | ((a >> 4) & 15) | ((a >> 5) & 2) | ((a >> 6) & 1);
return p;
}
*/
import "C"

import "fmt"

func main() {
a := 1
for i := 0; i < 8; i++ {
e := (a & 1) | (a & 2) | (a >> 1 & 4) | (a >> 4 & 8) // 1, 2, 4, 8
e |= ((a >> 1) & 2) | (a>>2)&1                       // 3
e |= ((a >> 2) & 4) | (a>>4)&1                       // 5
e |= ((a >> 3) & 4) | (a>>4)&2                       // 6
e |= ((a >> 4) & 4) | ((a >> 5) & 2) | (a>>6)&1      // 7
fmt.Println(e)
a <<= 1
}
b := 1
for i := 0; i < 8; i++ {
a := b
e := a & 3 // (a & 1) | (a & 2)         // 1, 2
a >>= 1    // b>>1
e |= a & 6 // (a & 4) | (a & 2)                // 4, 3
a >>= 1    // b>>2
e |= a & 5 // (a & 1) | (a & 4)                 // 3, 5
// a >>= 1 // b>>3
e |= (a >> 1 & 4) // 6
a >>= 2           // b>>4
//e |= (a & 1)                     // 5
//e |= (a & 2)                     // 6
//e |= (a & 4)              // 7
//e |= (a & 8)                     // 8
e |= a & 15              // 5, 6, 7, 8
e |= (a>>1)&2 | (a>>2)&1 // 7
fmt.Println(e)
b <<= 1
}
c := 1
for i := 0; i < 8; i++ {
a := c
e := (a & 3) | ((a >> 1) & 6) | ((a >> 2) & 5) | ((a >> 3) & 4) | ((a >> 4) & 15) | ((a >> 5) & 2) | ((a >> 6) & 1)
fmt.Println(e, int(C.pos(C.int(a))))
c <<= 1
}

// faster ! really this is as fast as
//                1 bitwise shift operation,
//                1 bitwise 'AND' operation
//                .. followed by one array uplook
// (found out this is deBruijn style)
// 111 101 001 100 010 110 011 000 '1101000111' (839*(1<<i))>>6)&7
//

var deBruijnMap = [8]byte{4, 5, 2, 6, 3, 1, 8, 7} // ->{5, 2, 4, 0, 1, 3, 7, 6}
const mult = 839
for i := 0; i < 8; i++ {
a := 1 << uint(i)
fmt.Println(deBruijnMap[((mult*a)>>6)&7])
}

}

``````

# Go – running fixed number of concurrent go routines

This snippet is about the control of running a fixed number of concurrent worker functions concurrently.

Lets start with a basic version, that does no error checking at all and that will simply panic in case one of the concurrent processes crashes.

Snippet 1

``````
package main

import "fmt"

func main(){
parallel(func(x int) error {
fmt.Println("Parameter:", x)
return nil
}, []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, 3)
}

func parallel(fn func(int) error, sq []int, p int) error {
var q = make(chan bool, p)
defer func() { close(q) }()
for _, s := range sq {
q <- true
go func(s int) {
fn(s)
<-q
}(s)
}
for len(q) > 0 {
}
return nil
}
``````

The function parallel takes the function to run in parallel (fn), a slice of parameters to start the concurrent workers (sq) with and the number of workers, you want to run in parallel. First a channel q of the capacity p (the number of concurrent processes) is instantiated. The defer function will care for proper closing. The for-loop takes care for starting the go routines with the appropriate values. By filling up the channel q the loop execution is blocked if the capacity is exhausted and p processes are running. Each return of a goroutine receives once from q and thus allows for a new loop until all parameter values are issued to the worker functions. The first for-loop exits and the second for-loop cares that all coroutines to finish before parallel returns.

Make sure your function fn in calling parallel(fn, sq, p) meets the function type (=signature) and the value table is adjusted properly then you are done with.

Note, that Snippet 1 panics if any of the concurrent processes crashes. Furthermore the second for loop will run in an endless loop, if one of the go routines didn’t return because ‚<-q' won't happen than. Such a code works well if the function called concurrently is guaranteed to non-panic or block (or if the project is an a state, where such panicking helps to improve logic). Snippet 2 cares for recovery and returns general error information and information on the parameter value that resulted in the crash.

Snippet 2

``````
package main

import "fmt"
import "errors"

func main(){
err, errlist := parallel(func(x int) error {
fmt.Println(x, 100/x)
return nil
}, []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0}, 3)
if err != nil {
fmt.Printf("Error! -> %v\n", err)
for _, err := range errlist {
fmt.Println("  ", err)
}
}
}

func parallel(fn func(int) error, sq []int, p int) (err error, errlist []error) {
var q = make(chan bool, p)
var e = make(chan error, len(sq))
defer func() {
close(q)
close(e)
}()
for _, s := range sq {
q <- true
go func(s int) {
defer func() {
if P := recover(); P != nil {
e <- errors.New(fmt.Sprintf("func(%v) crashed: %v", s, P))
}
<-q
}()
fn(s)
}(s)
}
for len(q) > 0 {
}
for len(e) > 0 {
err = errors.New(fmt.Sprintf("%d concurrent process crashed", len(e)))
errlist = append(errlist, <-e)
}
return err, errlist
}

------------------------------
Output from running this code.
3 33
4 25
5 20
6 16
1 100
7 14
2 50
9 11
10 10
8 12
Error! -> 1 concurrent process crashed
func(0) crashed: runtime error: integer divide by zero
``````

This gives better control on crashes and allows the main process to proceed even in case one of the concurrent functions crashes. Anyway it does not care properly for a concurrent function not returning.

Furthermore errors are printed out after all processes finished, which might be inconvenient on long running processes.

In the next Snippet 3 errors are channeled out to a concurrent running receiver loop.

``````
package main

import "fmt"
import "errors"

func main(){
// -> routine 4 concurrent error / result output
errChan := make(chan error, 11)
//ergChan := make(chan int, 11) // enable concurrent result output
alldone := make(chan bool, 1)
go func() {
for done := false; !done; {
select {
case e := <-errChan:
fmt.Println("Error -> ", e)
// case ee := <-ergChan: // enable concurrent result output
//   fmt.Println("Result -> ", ee)
case done = <-alldone:
break
}
}
}()
// <-

parallel(func(x int) error {
r := 100 / x
fmt.Println(x, r)
// ergChan <- r
return nil
}, []int{1, 2, 3, 0, 4, 5, 0, 6, 0, 7, 8, 9, 10}, 3, errChan)

// let error output goroutine exit
close(alldone)

// ....
}

// func parallel with errors returned through an error channel
func parallel(fn func(int) error, sq []int, p int, eC chan error) {
var q = make(chan bool, p)
defer func() {
close(q)
}()
for _, s := range sq {
q <- true
go func(s int) {
defer func() {
if P := recover(); P != nil {
eC <- errors.New(fmt.Sprintf("func(%v) crashed: %v", s, P))
}
<-q
}()
eC <- fn(s)
}(s)
}
for len(q) > 0 {
}
}
``````

I am aware that there is a number possibilities to make sure the number of concurrent running processes remains stable including the use of patterns to loop with a partial number of wait groups or monitoring a running counter and the like. None the less i think such use of channels is a particular elegant way to manage this problem.

# GO: passing Arrays & Slices to functions

When passing Arrays as parameters to functions some specialities need to be cared of. Go’s documentation stated, that arrays will be copied.

You would assume, the following function would, according to the steps, work like this: copy the array (when passing), sort the copy and return the median without changing the original array ‚l‘.

``````

package main

import (
"fmt"
"sort"
)

func arrayMedian(list []int) (median int) {
lenAR := len(list)
if lenAR == 0 {
return 0
}
sort.Ints(list)
if lenAR%2 == 0 {
return (list[lenAR/2-1] + list[lenAR/2]) / 2
}
return list[lenAR/2]
}

func main(){
l := []int{0,3,4,1,0,9,6,3,9,8}
fmt.Println(l, arrayMedian(l), l)
}

``````

Surprise – if looking at the output, you’ll find the original array ‚l‘ is sorted now.

Why? I guess, passing l by ‚arrayMedian(l)‘ didn’t pass the original array (or generates a copy) but passes a slice over ‚l‘ (rsp: a copy of the slice over ‚l‘), what actually means, that pointers to the ‚l’s list members are passed. The manipulation (here: sorting) is performed on the original array.

What you need to do is this instead:

``````
func arrayMedian(list []int) (median int) {
lenAR := len(list)
if lenAR == 0 {
return 0
}

ar := make([]int, lenAR)
copy(ar, list[:])

sort.Ints(ar)
if lenAR%2 == 0 {
return (ar[lenAR/2-1] + ar[lenAR/2]) / 2
}

return ar[lenAR/2]
}
``````

Though you produce a copy manually, sort the copy and return the result by leaving the original array ‚l‘ unchanged.

# How to include binary data into HTML5

… without getting cross-site-scripting problems on local files / server less testing.

For some 3D data representation i needed some MB binary 3D data to be included in the HTML side for further use in threejs. The file should be useful for standalone opening after email-sending – loading data from a fileserver wasn’t a an option though. On the other hand writing 8bit data points into asciitext wasn’t an option either, because such file fast becomes to big to be handled properly: each datapoint 8bit needs to be represented by 1-3bytes plus separator or by 3 bytes fixed length and both would pump up the file size. Another option would be a base64 encoding of the raw binary data which also might be compressed (zipped) before encoding resulting in an about 1.3 larger b64 asciitext, that can be unzipped and parsed to regain the data. This solution is smart but involves „unzipping to get the asciitext“ meaning that there has to be imported/bundled a fast and reliable javascript zip-library.

This is what i finally came up with:
1. write the 8bit binary data into a png file
2. base64 encode the resulting run-length compressed png file
3. use `<img src="data:image/png;base64,....">` to include that into the html5 file
4. create a hidden canvas of appropriate dimension and use context.drawImage and context.getImageData to extract the binary data which is now stored in an Uint8ClampedArray
5. calculate the needed Float32Array(s) for threejs from that Uint8ClampedArray

Note on step 1: you’ve the choice to use all 24bit of the pixel matrix in png (four 8bit binary data -> 1 pixel in png) and have some data length information elsewhere in your javascript to manage padding problems that might come up eventually. The lazy way is to encode only 1 Byte per pixel (grayscale png) and rely on the run length compression to deal with the resulting duplications. In the latter case, make sure you extract each forth value from the canvas context.getImageData method result.

This python code will provide you with the base64 encoded png data:

``````
from PIL import Image
import base64

fle = file("testdata.bin") # binary data: 12960000 bytes
im.save("testdata.png")

b64 = '<img id="dimg" src="data:image/png;base64,%s">'%b64
file('testdata64.html','wb').write(b64).close()

``````

# a faster bloomfilter for go/golang

a bloom filter is a structure that is designed to register bit pattern in a way, you can securely say the bit pattern you present to the bloom filter is unique and unknown to the filter if the filter returns that. Unfortunately you cannot invert this phrase: if the bloom filter response marks the bit pattern to be included („known“) to the filter, there is a certain possibility that this is factual wrong.

To get an idea about bloomfilters and how they work have a look here:
https://en.wikipedia.org/wiki/Bloom_filter
and here: https://de.wikipedia.org/wiki/Bloom_filter
and do not miss the great links provided at the end of the articles.

There is a range of bloom filters implemented in go/golang (see https://github.com/search?utf8=✓&q=bloom+filter+language%3AGo&type=Repositories&ref=advsearch&l=Go).

This said i had my own ideas about what is fast in bloom filters and the result is this:
https://github.com/AndreasBriese/bbloom

# go / golang (super) fast PRNG: BREEZE

i became unhappy with the usual go PRNGs including salsa and the like. Despite knowing about being foolish to take such a task i did create a deterministic chaos based random generater (CBRNG) that produces random bits (tested with the NIST package) and is faster than go’s standard random generator, salsa20 and of course way faster than go’s crypto/random package.

you may find this and a lot of information about the how and why and however else and speed …
at my github site: https://github.com/AndreasBriese/breeze
and there is a pdf summary too: https://github.com/AndreasBriese/breeze/blob/master/breeze.pdf

!! Do not oversee the fact, it is not so far cryptoanalysed by any third party !!

# Hash mich – Nachtrag zu PRNGs als Hashgeneratoren

In Ergänzung zu den Hashfunktionen hier

Auch Pseudo-Random-Number-Generatoren PRNG können grundsätzlich dazu eingesetzt werden, Hashwerte zu erzeugen.

PRNGs erzeugen ausgehend von einem Seed eine feste Abfolge von zufällig verteilten Zahlen, die man dann zu einem Hashwert beliebiger Länge kombinieren kann. Ein Problem können sehr kurze Strings sein, die gehasht werden sollen, da, wie gesagt, erst eine ausreichend großer Seed nötig ist, um den PRNG zu initialisieren.

SipHash https://131002.net/siphash/ von Jean-Philippe Aumasson und Daniel J. Bernstein (der u. a. Salsa20 PRNG für eine kryptologische Stream-Verschlüsselung entwickelt hat, ist ein solcher PRNG, der für kurze Eingaben optimiert wurde. SipHash ist nach Angaben der Verfasser etwa genauso schnell wie MurmurHash3.

Update:
SipHash hat mich überzeugt. Es ist schnell und anscheinend ziemlich Kollisionsresistent. Ich konnte BruteForce jedenfalls keine Kollisionen für strings mit Länge 8 und 16 finden.

# Hash mich – eine kleine Sammlung zu Hash-Algorithmen

Hashfunktionen begegnet man überall, wo es darum geht, Zeichenketten (z.B. Nutzernamen oder Passwörter) oder beliebige Daten (z.B. Download – Archive) voneinander zu unterscheiden. Oft werden Hashs im Hintergrund gerechnet, ohne dass der User das sieht. Anders beim Download von Programmen über das Internet: Hier wird auf der Downloadseite oft ein Hashwert des Downloads (syn. Hash- oder Programm-„Signatur“) angegeben, damit man nach dem Herunterladen (und vor dem Starten des Programms) noch einmal prüfen kann, ob das Programm vollständig und unverändert geladen wurde. Hashfunktionen sind vor allem im Verborgenen unverzichtbar – sie übernehmen das Encoding/Decoding von Zeichenfolgen zu Hashtables, die der schnellen Zuweisung von Befehlen zu Codes im Kern der Programmiersprachen und beim Kompilieren dienen (Wer mehr dazu wissen will, findet hier einen Videomitschnitt vom 29. CCC-Kongress, der das Dilemma (Hash-Table Flooding) „schlechter“ Hashfunktionen verdeutlicht.

Das Berechnen des Hashwerts kann eine rechenintensive Aufgabe sein. Ein Hash-Algorithmus liest Daten schrittweise ein und verrechnet den Stream zu einem Hashwert, der je nach Güte und Art des Hashprogramms in einen „seltenen“ oder sogar „einzigartigen“ Zahlenwert besteht (oft im Hexadezimalformat ausgegeben).

Hashfunktionen allgemein werden nach der Länge des Ausgabewertes (Angabe in Bit) unterschieden, kryptologische Hashfunktionen liefern Hashs mit einer fixen Länge (z.B. SHA256->256Bits ; SHA512->512Bits) , andere Funktionen liefern Hashwerte bis zu einem Maximalwert.

Kryptologisch sichere Hashfunktionen sind unter anderem dahingehend optimiert, dass es keine – nicht einmal theoretische – Kollisionen gibt (Kollisionen sind gleiche Hashwerte für ungleiche Eingangsdaten). Außerdem sind die Algorithmen so gestaltet, dass zwei Eingaben, die sich nur sehr geringfügig unterscheiden, bereits stark unterschiedliche Hashergebnisse (Signaturen) ergeben. Dabei ist es wichtig, dass der Rechenweg so konzipiert ist, dass sie sogenannte „Einwegfunktionen“ darstellen und vom Hash nicht auf die Eingabedaten zurück gerechnet werden kann. Will man also von einer kryptologischen Signatur auf den Eingabewert zurückschließen, so ginge dies nur, wenn man eine Tabelle mit allen möglichen Eingabewerten und zugehörigen Hash-Ausgaben hat. Liegen solche Tabellen (z.B. „Rainbow-Tables“ für Strings in typischer Passwortlänge) einmal vor, so ist diese Hashfunktion natürlich nicht mehr sicher und sollte im sicherheitsrelevanten Zusammenhängen – zum Beispiel fürs Speichern von Passwörtern – nicht weiter benutzt werden: MD5, SHA-1; Weiteres siehe: https://de.wikipedia.org/wiki/Kryptologische_Hashfunktion ).

Erwähnenswert: Zu den ganz neuen kryptologischen Hashfunktionen gehören BLAKE2s (32 Bit Maschinen) und BLAKE2b (64 Bit Maschinen) https://blake2.net, die Jean-Philippe Aumasson et al. unter Verwendung von Daniel Bernsteins ChaCha Code entwickelt haben. Blake2 Hashfunktionen sind so schnell wie MD5 oder SHA-1, im Unterschied zu vorgenannten sind sie jedoch (derzeit) kryptologisch sicher.

Nicht kryptologische Hashfunktionen

Im Gegenzug sind aufgrund zusätzlicher Rechenschritte kryptologische Hashfunktionen vergleichsweise langsamer als nicht kryptologische Hashfunktionen (Faktor 30x-300x). Für die Verarbeitung nicht sicherheitsrelevanter Daten, bei denen kryptologische Eigenschaften des Hashs keine Rolle spielen, werden darum einfachere (= schnellere) Hashfunktionen eingesetzt. Eventuell ist auch Kollisionsfreiheit weniger wichtig als Geschwindigkeit oder das Risiko von Kollisionen wird verringert, indem mehrere (zwei +) Hashs mit verschiedenen schnellen, aber nicht kollisionssicheren Hashfunktionen berechnet und kombiniert werden. Trotzdem speilt Kollisionssicherheit eine grosse Rolle und die neuesten Hash-Algorithmen punkten hier deutlich.

0815 Nutzen: Hashen jenseits von Passwort/Nutzernamen

Nehmen wir an, eine Reihe Bilder, die sich eventuell nur um den Farbwert einzelner Pixel unterscheiden, sollen daraufhin geprüft werden, ob sie exakt einer Referenz (Original) entsprechen. Ein „naiver“ Ansatz wäre, jedes der Bilder Pixel für Pixel mit der Referenz zu vergleichen. Geht es aber nur darum festzustellen, ob sich die Bilder von der Referenz unterscheiden, so ist die Verwendung eines Hashes die effektivere Lösung.

``````
Erstelle einen Hash der Referenz
Für jedes Bild
erstelle einen Hasch
vergleiche den Bild-Hash mit dem Referenz-Hash
gib zurück: gleich / ungleich

``````

Habe ich einen schnellen Hash-Algorithmus so kann ich die Vergleichsdaten auch in Segmente unterteilen und dann die Segment-Hashs untersuchen und vergleichsweise resourcen-sparsam und schnell Unterschiede lokalisieren.

``````
Erstelle einen Hash der Referenz
Für n-Segmente der Referenz
erstelle je einen Referenz-Segment-Hash
Für jedes Bild
erstelle einen Hasch
vergleiche den Bild-Hash mit dem Referenz-Hash
wenn ungleich
für n-Segmente des Bildes
erstelle Bild-Segment-Hash
vergleiche Bild-Segment-Hash mit Referenz-Segment-Hash
gib zurück: ungleiche Segmente

``````

Statt ganze Bilder, Pixel für Pixel mit einer Referenz zu vergleichen, ist dann nur noch ein Vergleich der Segmente, die ungleiche Hashwerte hatten, nötig, um unterschiedliche Pixel exakt zu lokalisieren.

Welche Hashfunktion ist die richtige für meinen Zweck

Viele Hashfunktionen sind optimiert für die schnelle Verarbeitung großer Datenmengen. Das geschieht z.B. durch die Verarbeitung von Byte-Gruppen in einem Durchgang. Dass die Hashrechnung selbst etwas aufwendiger ist, fällt dabei dann weniger ins Gewicht, als bei Funktionen, die einen Stream/String Byte für Byte verrechnen. In der Gegenüberstellung zu Googles xxHash http://code.google.com/p/xxhash/ finden sich Vertreter dieses (neueren) Hashtyps auf den oberen sechs Plätzen der Rankingtabelle. Siehe auch hier: http://brainspec.com/blog/2012/10/29/fast-hashing-with-cityhash/ Zur Entwicklung von Hashfunktionen neueren Typs, die bei großen Datenmengen auch die Möglichkeiten aktueller Prozessoren zur parallelen Berechnungen ausnutzen: http://web.stanford.edu/class/ee380/Abstracts/121017-slides.pdf

Für eine Aufgabe, wie die oben geschilderten Vergleiche von Bilddateien, können diese „modernen“ hochperformanten Hashfunktionen gut geeignet sein. Wenn man allerdings nur kurze Strings hashen muss (z.B. IP-Adressen oder Log-Einträge) und ohnehin nur 32Bit oder 64Bit Ergebnisse braucht, waren die Hash-Funktionen 2. und 3. Generation bei meinen eigenen Benchmarks allesamt langsamer als SDBM, FNV oder DJB2, da die Byte-Gruppen-Verarbeitung einen recht großen Overhead (Initialisierung, Finalisieren) mitbringt.

Schnelle, nicht kryptologische Hashfunktionen

Im Folgenden eine Liste mit Links zu verschiedenen Webseiten, die sich mit Hash-Berechnungen beschäftigen:

FNV-Hash Family http://www.isthe.com/chongo/tech/comp/fnv/index.html based on prime calculations.

Bob Jenkins Sites http://burtleburtle.net/bob/

• Hash-/Block-Cipher http://burtleburtle.net/bob/hash/index.html
• lookUP3 http://burtleburtle.net/bob/c/lookup3.c
• SpookyhashV2 (2012) http://burtleburtle.net/bob/hash/spooky.html
und Grundlagen: http://burtleburtle.net/bob/hash/integer.html Integer Hashes mit verschiedenen Beispielen.
• Pearson Hash mit random Hashtable (klassisches BASIC) http://burtleburtle.net/bob/hash/pearson.html
• Arash Partow Zusammen-&Gegenüberstellung klassischer Hashfunktionen http://partow.net/programming/hashfunctions/index.html

Die Seite diskutiert verschiedenste Hashfunktionen und erlaubt den Download in verschiedenen Programmiersprachen z.B. CPP oder Python:

``````
// citation: An algorithm proposed by Donald E. Knuth in The Art Of Computer Programming Volume 3,
// under the topic of sorting and search chapter 6.4.
def DEKHash(key):
hash = len(key);
for i in range(len(key)):
hash = ((hash << 5) ^ (hash >> 27)) ^ ord(key[i])
return hash
``````

DEKHash in Go:

``````
func (bl Bloom) DEKHash(b *[]byte) (hash uint64) {
hash := uint64(len(*b))
for _, c := range *b {
hash = ((hash << 5) ^ (hash >> 27)) ^ uint64(c)
}
return hash
}
``````

http://www.cse.yorku.ca/~oz/hash.html – DJB2 und SDBM-Hash Funktionen in C

http://code.google.com/p/xxhash/ xxHash und ein Benchmarking verschiedener Hash-Funktionen: xxHash, cityHash, lookUp3, SpookyHash2, Murmur3, FNV …

Eine ausführliche Diskussion verschiedener Hashfunktionen mit vielen Links findet sich auch hier:http://blog.reverberate.org/2012/01/state-of-hash-functions-2012.html

# Fast prime-generators with python

Euler project „Project Euler“ http://projecteuler.net inspired some coders to think about prime generation in python. Even if the primes are already known, the pure python implementations are interesting to get information about fast computation models for big number arrays.

Das „Project Euler“ http://projecteuler.net hat eine Reihe Programmierer inspiriert, sich mit der Frage der Erzeugung von Primzahlen auseinanderzusetzen. Das ist in erster Linie ein akademisches Unterfangen, weil die entsprechenden Primzahlen (<10**10 u.Ä.) natürlich bereits bekannt sind. Trotzdem eine spannende Aufgabe, fand ich, und habe eine Routine programmiert, von der ich hoffte, sie könne im Vergleich mithalten, indem sie durch Deduction die Anzahl der Kalkulationen drückt. Hat nur bedingt geklappt.

Hier ist der Sieger-Code von Robert William Hanks:

``````
def rwh_primes(n):
# http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
""" Returns a list of primes &lt; n """
sieve = [True] * n
for i in xrange(3,int(n**0.5)+1,2):
if sieve[i]:
sieve[i*i::2*i]=[False]*((n-i*i-1)/(2*i)+1)
return [2] + [i for i in xrange(3,n,2) if sieve[i]]
``````

``````
def rwh_primes1(n):
# http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
""" Returns a list of primes &lt; n """
sieve = [True] * (n/2)
for i in xrange(3,int(n**0.5)+1,2):
if sieve[i/2]: sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1)
return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]]
``````

``````
def rwh_primes2(n):
# http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
""" Input n&gt;=6, Returns a list of primes, 2 &lt;= p &lt; n """
correction = (n%6&gt;1)
n = {0:n,1:n-1,2:n+4,3:n+3,4:n+2,5:n+1}[n%6]
sieve = [True] * (n/3)
sieve[0] = False
for i in xrange(int(n**0.5)/3+1):
if sieve[i]:
k=3*i+1|1
sieve[ ((k*k)/3) ::2*k]=[False]*((n/6-(k*k)/6-1)/k+1)
sieve[(k*k+4*k-2*k*(i&amp;1))/3::2*k]=[False]*((n/6-(k*k+4*k-2*k*(i&amp;1))/6-1)/k+1)
return [2,3] + [3*i+1|1 for i in xrange(1,n/3-correction) if sieve[i]]
``````

However – meine Lösung ist auf einem MBPro15/i7 als schnellste hinter RWHs Lösungen 1 und 2 dennoch ziemlich gut weggekommen:

``````
def primeSieveSeq(MAX_Int):
if MAX_Int > 5*10**8:
import ctypes
int16Array = ctypes.c_ushort * (MAX_Int >> 1)
sieve = int16Array()
#print 'uses ctypes "unsigned short int Array"'
else:
sieve = (MAX_Int >> 1) * [False]
#print 'uses python list() of long long int'
if MAX_Int < 10**8:
sieve[4::3] = [True]*((MAX_Int - 8)/6+1)
sieve[12::5] = [True]*((MAX_Int - 24)/10+1)
r = [2, 3, 5]
n = 0
for i in xrange(int(MAX_Int**0.5)/30+1):
n += 3
if not sieve[n]:
n2 = (n << 1) + 1
r.append(n2)
n2q = (n2**2) >> 1
sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
n += 2
if not sieve[n]:
n2 = (n << 1) + 1
r.append(n2)
n2q = (n2**2) >> 1
sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
n += 1
if not sieve[n]:
n2 = (n << 1) + 1
r.append(n2)
n2q = (n2**2) >> 1
sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
n += 2
if not sieve[n]:
n2 = (n << 1) + 1
r.append(n2)
n2q = (n2**2) >> 1
sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
n += 1
if not sieve[n]:
n2 = (n << 1) + 1
r.append(n2)
n2q = (n2**2) >> 1
sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
n += 2
if not sieve[n]:
n2 = (n << 1) + 1
r.append(n2)
n2q = (n2**2) >> 1
sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
n += 3
if not sieve[n]:
n2 = (n << 1) + 1
r.append(n2)
n2q = (n2**2) >> 1
sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
n += 1
if not sieve[n]:
n2 = (n << 1) + 1
r.append(n2)
n2q = (n2**2) >> 1
sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
if MAX_Int < 10**8:
return [2, 3, 5]+[(p << 1) + 1 for p in [n for n in xrange(3, MAX_Int >> 1) if not sieve[n]]]
n = n >> 1
try:
for i in xrange((MAX_Int-2*n)/30 + 1):
n += 3
if not sieve[n]:
r.append((n << 1) + 1)
n += 2
if not sieve[n]:
r.append((n << 1) + 1)
n += 1
if not sieve[n]:
r.append((n << 1) + 1)
n += 2
if not sieve[n]:
r.append((n << 1) + 1)
n += 1
if not sieve[n]:
r.append((n << 1) + 1)
n += 2
if not sieve[n]:
r.append((n << 1) + 1)
n += 3
if not sieve[n]:
r.append((n << 1) + 1)
n += 1
if not sieve[n]:
r.append((n << 1) + 1)
except:
pass
return r
``````

Auf jeden Fall bleibt festzuhalten, dass in python der Fill mit Array Access über Indexranges array[start:stop:step] = [True]*(((MAX_Int >> 1) – n2q – 1) / n2 + 1) jeder Schleifenkontrolle in Bezug auf processing-speed deutlich überlegen ist.

# Speed-comparison of two different designs of a prime-number-generator

Eventually i needed some prime numbers to play around with Bloom filtering.
The Python – script (see below) will produce primes below 2**x base number by stepping backward using the step parameter.
python primes.py <number of file> <2**x exponent x> <step> <number of primes to produce>

if the <number of file> parameter is a character output to a file will be omitted and the primes will print to stdout instead.

<number of primes to produce> defaults to 10

I tested the performance of a single threaded and multi-threaded approach on some PC of various age. The outcome was interesting:

On one hand the script performance benefits very much from improvements of CPU architecture. Nonetheless clock speed and number of real cores seem to be of highest importance.

``````
#! /usr/bin/python
# procuces scripts < 2**x by testing in a by
import os
import sys
import subprocess
import pprint
import time

cnt = totcnt = 0
erg = []

# check 4 gmpy
try:
# raise
from gmpy import mpz
print "Message: Using gmpy/GMP mpz.is_prime instead of openSSL prime. (up to 10times faster)"
except:
print """Message:
If you try to produce many or really large primes,
consider installing GMP ( http://gmplib.org )
and gmpy/gmpy2 ( http:http://www.aleax.it/gmpy.html )"""

def __init__(self, num):
self.num = num

def run(self):
global erg, cnt
prm = check(self.num)
if prm:
erg.append(prm)
cnt += 1

def check(num):
r = None
try:
if mpz(num).is_prime() == 1:
r = num
except:
print '#', num, '#'
else:
e = subprocess.Popen(['/usr/bin/openSSL', 'prime', num], stdout=subprocess.PIPE)
if e.communicate()[0][-9:-7] == "is":
r = num
return r

def longnumget(start, step):
start = str(start+step)
step = 2*step
lenstep = 2*len(str(step))
def numSeperator(numAsString, lenstep):
formatter = '%%0%ii' % lenstep
frst, secnd = numAsString[:-lenstep], start[-lenstep:]
diff = int(secnd)-step
secnd = formatter % diff
r = frst + secnd
if diff < 0:
r = numSeperator(numAsString, lenstep+1)
return r
while True:
start = numSeperator(start, lenstep)
while start[-1] == '5':
start = numSeperator(start, lenstep)
yield start

def shortnumget(start, step):
start = start+step
step = 2*step
while True:
start -= step
while str(start)[-1] == '5':
start -= step
yield str(start)

if __name__ == '__main__':
if len(sys.argv) == 5:
p, seqNum, base2exp, step, count = map(str, sys.argv)
if count:
count = int(count) or 10
step = abs(int(step))
if step % 2 == 0:
print("Step must be odd!")
sys.exit()
if int(base2exp) < 4000:
numget = shortnumget
else:
numget = longnumget
print "custom string-cut partitional substraction"
startnum = mpz('0b1'+int(base2exp)*'0', 0)
else:
startnum = eval('2**'+base2exp)
nums = numget(startnum, step)
sTime = time.time()
while cnt <= count:
# uncomment the next 2 lines to test of the single threaded approach
# check(nums.next())
# totcnt += 1
#
# uncomment next 5 lines to test the threaded approach
t = checkr(nums.next())
t.start()
totcnt += 1

print 'Time elapsed:', time.time() - sTime, 'seconds'
print totcnt, 'numbers checked for prime'
print len(erg), 'primes found (', round(100.0*len(erg)/totcnt, 1), '%)'

try:
seqNum = int(seqNum)
with file('primes_%s_%sK_%s.txt' % (seqNum, count/1000, base2exp), 'wb') as outFle:
for i in xrange(len(erg)):
print >> outFle, '2**%s-%s' % (base2exp, startnum - int(erg[i])), erg[i], hex(int(erg[i]))
except Exception as e:
pp = pprint.PrettyPrinter()
pp.pprint(erg)

``````