Project Euler 12

Bashar

Ich hab nicht mit Primzahlfaktorisierung gearbeitet, sondern wirklich mit allen Teilern.

ich hab's spaßeshalber in pharo smalltalk implementiert. 8-12 Millisekunden Rechenzeit und ca 12-16 Millisekunden mehr mit Ausgabe des Ergebnisses.
:xmas1:

Bashar schrieb:

Ich hab nicht mit Primzahlfaktorisierung gearbeitet, sondern wirklich mit allen Teilern.

Zeig mal bitte

Bashar

Tim schrieb:

Zeig mal bitte

function [n,m,d] = Euler12(N)
% Returns the smallest n such that the n-th triangle number (m = n(n+1)/2) has
% at least N divisors

n1 = 1;
d1 = 1;
n2 = 1;
d2 = 1;

D = 2;
while d1*d2 < N
    temp = n1;
    n1 = n2;
    n2 = temp + D;

    d1 = d2;
    d2 = Divisors(n2);

    if D == 1
        D = 2;
    else
        D = 1;
    end
end

n = n1;
m = n1*n2;
d = d1*d2;

function d = Divisors(n)
% returns the number of divisors of n
d = 1;
for i = 2:n
    if mod(n, i) == 0
        d = d + 1;
    end
end

Offensichtlich nicht optimal ich habs kurz vor (nicht nach;)) der :xmas1: :xmas2: Weihnachtsparty :xmas2: :xmas1: geschrieben und aufgehört als es lief. Jetzt nochmal mit Octave probiert, das bricht sich anscheinend stundenlang einen ab (was mir ehrlich gesagt spanisch vorkommt, ich hätte nicht mit Geschwindigkeitsunterschieden Faktor >100 gerechnet). Also besser vielleicht doch mit Primzahlzerlegung versuchen .... Und mit besseren Namen blabla :xmas1:

22 millisekunden

mult := [ :n :p || e q | 
	e := 0. q := p.
	[ n \\ q = 0 ] 
		whileTrue: [ 
			e := e+1. 
			q := q*p ]. 
	e+1 ].
primes := Integer primesUpTo: 19.
numberOfDivisors := [ :n | 
	primes 
		inject: 1 into: [ :prod :prime | 
			prod * (mult value: n value: prime) ] ].
run := [ | n | n := 1.
	[ | d | 
		d := numberOfDivisors value: n*(n+1)/2.
		d < 500 ] 
			whileTrue: [ n := n+1 ].
		Transcript  
			show: n asString ].
Time millisecondsToRun: [ run value ].

das Smiley in Zeile 1 steht für "Doppelpunkt p" :xmas2:

7 millisekunden und 5 ms mit -O3 bei mir - eig gar nicht so viel schneller als in smalltalk

#include<iostream>
typedef unsigned int Int;
Int mult(Int n, Int p){
  Int e = 0, q = p;
  while(!(n%q)){
    e++; q *= p;
  }
  return e+1;
}
Int Primes[] = { 2, 3, 5, 7, 11, 13, 17 };
Int numberOfDivisors(Int n){
  Int prod = 1, i = 0;
  while(i < 7)
    prod *= mult(n, Primes[i++]);
  return prod;
}
int main(void){
  Int n = 1;
  while(numberOfDivisors(n*(n+1)/2) < 500)
    n++;
  std::cout << n << std::endl;
  return 0;
}

Michael E.

Mach noch aus dem cout ein printf oder lass wenigstens endl weg. Wie viel schneller willst du es denn noch haben?

knivil

!rr!rr_. schrieb:

smalltalk implementiert. 8-12 Millisekunden Rechenzeit und ca 12-16 Millisekunden ... 7 millisekunden und 5 ms mit -O3 bei mir - eig gar nicht so viel schneller als in smalltalk ...

Nur leider helfen die Zahlen nicht wirklich beim Vergleich. Hier weiss niemand, welche Hardware du benutzt. Betriebsysteme koennten sich auch auf die Zeit auswirken.

Schaut man sich das pdf an (sichtbar, wenn das Problem gloest wurde) wird dort geschrieben:

When the above algo is written in assembly (including the generation of primes up to 1000) and almost fully optimized, it runs in less than 1 millisec on a P4-1500. It should easily run in less than 10 millisec when written in most modern compiled languages.

knivil schrieb:

Nur leider helfen die Zahlen nicht wirklich beim Vergleich. Hier weiss niemand, welche Hardware du benutzt. Betriebsysteme koennten sich auch auf die Zeit auswirken.

darum hat er ja den code geposted -.-

knivil

Und das soll es besser machen? Bei einem Quelltext weiss ich die Sprache sicher, bei den anderen ... hinzukommt Compiler/Interpreter/VM/Architektur ... etc.

nein, wenn der code zu allem vorliegt, kann das jeder bei sich zu hause auf seinem rechner testen und vergleichen und hat somit, da man sein eigenes system kennt, einen guten eindruck davon, wie die einzelnen impementierungen zueinander stehen - !rr!rr_.s zahlen geben einen ersten eindruck davon.

volkard

!rr!rr_. schrieb:

22 millisekunden

mult := [ :n :p || e q | 
	e := 0. q := p.
	[ n \\ q = 0 ] 
		whileTrue: [ 
			e := e+1. 
			q := q*p ]. 
	e+1 ].
primes := Integer primesUpTo: 19.
numberOfDivisors := [ :n | 
	primes 
		inject: 1 into: [ :prod :prime | 
			prod * (mult value: n value: prime) ] ].
run := [ | n | n := 1.
	[ | d | 
		d := numberOfDivisors value: n*(n+1)/2.
		d < 500 ] 
			whileTrue: [ n := n+1 ].
		Transcript  
			show: n asString ].
Time millisecondsToRun: [ run value ].

das Smiley in Zeile 1 steht für "Doppelpunkt p" :xmas2:

Die ersten Primzahlen bis 19 zu berechnen und vorher schon zu wissen, daß man nur 19 braucht, heißt, daß man das Ergebnis schon kennt.
Warum nicht gleich 76576500 anzeigen und fertig?

Außerdem ist bei so wenigen Millisekunden ein Messen kaum noch sinnvoll. Allein das Programm zu starten (neuer Prozess) ist ja schon in dieser Gegend. Oder? Wenn ich den Programmstart herausnehme und die langsame synchrone Ausgabe auf die Konsole und die Primzahlen bis 19 nehme, lande ich mit campers Trick und ohne Michael E.s Trick (der würde nochmal ca Faktor 2 machen) mit C/C++ bei 617µs.

volkard schrieb:

Die ersten Primzahlen bis 19 zu berechnen und vorher schon zu wissen, daß man nur 19 braucht, heißt, daß man das Ergebnis schon kennt.

Gut beobachtet! Das Programm ist schon leicht optimiert. Es liefert die gesuchte Zahl in vernünftiger zeit, das reicht mir.

Ich habe natürlich auch eine Komfort-Version, die kein Wissen über den größten Primfaktor voraussetzt, sondern nach und nach die Primfaktoren bis 2^r zufügt, unter der gut bestätigten Heuristik, daß die gesuchte Zahl aus vielen kleinen Primfaktoren bestehen wird.

Da es 564 Primzahlen < 2^12 gibt, und die gesuchte Zahl schwerlich mehr als 500 verschiedene Primfaktoren haben kann, reicht es, r <= 12 zu untersuchen, der Suchraum ist also nicht allzugroß, und das Programm auch nicht unendlich viel länger unterwegs.

volkard schrieb:

Außerdem ist bei so wenigen Millisekunden ein Messen kaum noch sinnvoll. Allein das Programm zu starten (neuer Prozess) ist ja schon in dieser Gegend. Oder?

Ja - und? dies ist ja auch kein Kolloquium über Meßtechnik :xmas1: 10 ms oder 20 oder 200, merkt man keinen unterschied. Bei 500000 Primteilern wäre das wahrscheinlich anders.