Code: Alles auswählen
#!/usr/bin/env python
# coding: utf8
from __future__ import absolute_import, division, print_function
from math import sqrt
def sieve(limit):
is_prime = [True] * limit
is_prime[0] = is_prime[1] = False
for i in xrange(2, int(sqrt(limit)) + 1):
if is_prime[i]:
for j in xrange(i * i, limit, i):
is_prime[j] = False
return (i for i, t in enumerate(is_prime) if t)
def main():
print(sum(sieve(2000000)))
if __name__ == '__main__':
main()[codebox=c file=Unbenannt.c]#include <inttypes.h>
#include <stdbool.h>
#include <stdio.h>
static _Bool is_prime(uint_fast32_t candidate)
{
uint_fast32_t i;
for (i = 2; i < candidate; ++i) {
if (candidate % i == 0) return false;
if (candidate / i < i) break;
}
return candidate > 1;
}
int main(void)
{
uint_fast64_t sum = 0;
uint_fast32_t i;
for (i = 1; i < 2000000; ++i) {
if (is_prime(i)) {
sum += i;
}
}
printf("%"PRIuFAST64"\n", sum);
return 0;
}[/code]
Kompiliert mit GCC und Optimierungen wird die Testfunktion direkt in die Hauptfunktion eingefügt, so dass dort der Funktionsaufruf eingespart wird. Ich habe den generierten Quelltext mal mit sprechenderen Label-Namen versehen und ein wenig kommentiert:
[codebox=asm file=Unbenannt.asm] .intel_syntax noprefix
.section .rodata.str1.1,"aMS",@progbits,1
.format_string:
.string "%lu\n"
.section .text.startup,"ax",@progbits
.p2align 4
.globl main
main:
; candidate = 1
mov esi, 1
; sum = 0
xor edi, edi
; Align loop start to 16 byte boundary if max 10 bytes away
; or to 8 byte boundary
.p2align 4,,10
.p2align 3
.outer_loop:
; if candidate <= 2
cmp rsi, 2
jbe .L8
; if candidate is even but not <=2 it is not prime
test sil, 1
je .is_not_prime
; if candidate is three then it is prime,
; else i = 2 and run inner loop
cmp rsi, 3
mov ecx, 2
jne .inner_loop_inc
jmp .is_prime
.p2align 4,,10
.p2align 3
.inner_loop:
; div/mod candidate and i
xor edx, edx
mov rax, rsi
div rcx
; if remainder then not prime
test rdx, rdx
je .is_not_prime
; if result of division < i then candidate is prime
cmp rax, rcx
jb .is_prime
.inner_loop_inc:
; increase i and if not reached candidate then test i
add rcx, 1
cmp rcx, rsi
jne .inner_loop
.is_prime:
; sum += candidate
add rdi, rsi
.is_not_prime:
; increase candidate and test if upper limit is hit
add rsi, 1
cmp rsi, 2000000
jne .outer_loop
; print sum
mov rdx, rdi
mov esi, OFFSET FLAT:.format_string
mov edi, 1
xor eax, eax
call __printf_chk
; return 0
xor eax, eax
ret
.L8:
; if candidate is 1 then candidate = 2
; otherwise candidate stays 2
cmp rsi, 1
mov eax, 2
cmove rsi, rax
jmp .is_prime[/code]
Wie man sieht entspricht das ziemlich dem was DerTürke an Assembler gezeigt hat. Etwas schräg ist der erste Test und der Code bei `.L8`. Das hätte man als Mensch wahrscheinlich anders geschrieben. Letztlich fällt das bei der Laufzeit aber kaum ins Gewicht, denn es betrifft nur einen von zwei Millionen Schleifendurchläufen.
Interessant ist, dass der Compiler selbst gemerkt hat, das ungerade Kandidaten ausser der 2 nicht zu einer Addition auf die Summe führen und das deswegen mit einem billigen Bit-Test gesondert behandelt, um die teurere Division für jede zweite Zahl zu sparen.
Und das Ergebnis: Python ist fast doppelt so schnell.
Um mal einen Fusballtrainer zu zitieren: Schön spielen ist nichts, wenn das Resultat nicht stimmt. Man kann sich viel Mühe geben handgeklöppelten Assembler zu schreiben, und dafür sicher ein Fleissbienchen verdienen, aber wenn man dann *deutlich* von einer dynamisch interpetierten Programmiersprache überholt wird, wo sogar noch der Compilerlauf von Quelltext nach Bytecode für die VM mit in der Laufzeit enthalten ist, dann war das wohl nix. Aber dicke Töne spucken, andere hätten keine Ahnung. Süss.
.
.
Wenn man das nicht in Assembler macht, geht das sogar sehr einfach. Bei dem C-Programm einfach ein OpenMP-Pragma um die äussere Schleife zu parallelisieren: