staging.inyokaproject.org

Hello World hat geschrieben:

Und außerdem finde ich es ungerecht, dass sowohl die Python-Lösung schneller ist als C++. Zumal ich nicht so recht weiß, wie ich es optimieren soll. Der Profiler sagt, dass satte 54% der Laufzeit in std::reverse verbracht werden. Eine selbst geschriebene Reverse-Funktion für die Strings ist aber nur wenig schneller :/.
Bei Java seh ich ja noch ein, dass da mittels Laufzeitoptimierung noch einiges herausgeholt werden kann. Da kann man schön erkennen, wie der JIT so optimiert ☺

Falls es dich beruhigt: Bei Python verbringt man ca. 70% der Zeit mit der Reverse-Funktion 😀
Aus der ist aber auch nichs mehr rauszuholen. Ich habs mal mit einer Liste von Zahlen versucht, da eine Liste sehr viel günstiger umzudrehen ist, aber das ständige Listenschubsen hats dann mehr als ausgewogen.

Python ist komisch. Solang man dem Interpreter nur möglichst direkt sagt, was man will ist der Code abartig fix. 😀

meine ersten Zahlen:
196
295
394
493
592
689
691
788
790
879
887
978
986
1495

audax hat geschrieben:

Falls es dich beruhigt: Bei Python verbringt man ca. 70% der Zeit mit der Reverse-Funktion 😀

Ich hab einfach mal stupide mirror(n) mit einem Cache ausgestattet:

cache = {}

def mirror(n): 
	try:
		return cache[n]
	except:
		tmp = int(str(n)[::-1])
		cache.update({n: tmp})
		return tmp

~30% schneller bei mir.
Und wenn man auf Exception verzichtet...

cache = {}

def mirror(n): 
	if cache.hey_key(n):
		return cache[n]
	else:
		tmp = int(str(n)[::-1])
		cache.update({n: tmp})
		return tmp

...ist es nochmal schneller.

*hust*
NIEMALS ein bare-except. 😀

cache = {}

def mirror(n):
   try:
      return cache[n]
   except KeyError:
      tmp = int(str(n)[::-1])
      cache.update({n: tmp})
      return tmp 

coxran hat geschrieben:

Meine C++ Version, die ich momentan aber leider nicht posten kann (evtl. heut Abend), findet meiner Ansicht nach auch zuviele Zahlen. Zum Beispiel die 89 und die 98, obwohl laut Wikipedia (Lychrel-Zahl) 196 die kleinste Lychrel Zahl ist. Oder sind 100 Iterationen einfach noch nicht genug?

Doch die sind bei weiten genug die erste Zahl bei der man über 100 Iterationen braucht ist 1.005.499.526 dort brauch man genau 109 ☺

coxran hat geschrieben:

Was sind eure ersten Lychrel Zahlen?

196 wie sich das gehört 😛

Bei Geschwindigkeitsvergleichen ist es (für mich) immer interessant, wie die gegen meine C-Implementierung ausfallen. Denn die 14 Minuten für die Prüfung der ersten 10000 Zahlen dauert das nur auf'm C64. Für alle 100000 braucht das Programm bei mir auf dem PC nur 0,36 Sekunden (Ausgabe nach /dev/null umgeleitet).

@Blattlaus: Du kannst das has_key() noch mit dem in-Operator ersetzen, dann sparst Du einmal dynamisch die Methode ermitteln pro Aufruf.

öh...dann stimmt bei meiner rubylösung was net 😀 (gut, ich hab mir den wikipedia artikel zur lychrel zahl auch noch net allzu gut angeguckt *ggg*)

Marc 'BlackJack' Rintsch hat geschrieben:

Bei Geschwindigkeitsvergleichen ist es (für mich) immer interessant, wie die gegen meine C-Implementierung ausfallen. Denn die 14 Minuten für die Prüfung der ersten 10000 Zahlen dauert das nur auf'm C64. Für alle 100000 braucht das Programm bei mir auf dem PC nur 0,36 Sekunden (Ausgabe nach /dev/null umgeleitet).

Die gewinnt natürlich haushoch 😀
Bei mir mit 0.5 Sekunden

€dit:
Wargh. Das ding lebt ja von globalen Variablen 😀
Es wirklich nur auf Geschwindigkeit getrimmt 😉

So ich habs mal probiert das ganze im Mips-Assembler zu schreiben... So richtig ist es mir allerdings nicht gelungen...
Ich kann zwar einzelne Zahlen überprüfen... aber die die letzte Schleife(1 - 100000) will nicht so wie ich das möchte 👿

Hier ist mal was ich bis jetzt bereits habe:

.data
	var: 	.word 1,9,6
	nix: 	.word 0
	nl:		.asciiz "\n"
.text
main: 		la $s1 var
			move $s4 $s1
			j lychrel
end:		li $v0 10
			syscall


lychrel: 	li $a1 0x00000015
lychloop:	beq $a1 $zero print
			jal spiegel
			jal plus
			jal pali
			beq $a2 1 endlychrel
			sub $a1 $a1 0x00000001
			j lychloop
endlychrel:	j end


print:		lw $a0 0($s4)
			li $v0 1
printloop:	beq $a0 $zero endprint 
			syscall					
			add $s4 $s4 0x00000004
			lw $a0 0($s4)
			j printloop
endprint: 	li $v0 4
			la $a0 nl
			syscall
			j end


pali:		move $a3 $ra
			move $s7 $s0
			move $s1 $s0
			jal last
			lw $t1 0($s0)
			lw $t2 0($s7)
paliloop:	bne $t1 $t2 notpali
			bgt $s0 $s7 endpalit
			add $s0 $s0 4
			sub $s7 $s7 4
			lw $t1 0($s0)
			lw $t2 0($s7)
			j paliloop
endpalit:	move $ra $a3
			li $a2 1
			jr $ra
notpali:	move $ra $a3
			li $a2 0
			jr $ra


spiegel:	move $a3 $ra
			move $s7 $s1
			jal last
			lw $t4 0($s7)
			li $s2 0x100400c0
sploop:		beq $t4 $zero spend
			sw $t4 0($s2)
			add $s2 $s2 4
			sub $s7 $s7 4
			lw $t4 0($s7)
			j sploop
spend:		li $s2 0x100400c0
			move $ra $a3
			jr $ra

plus:		move $a3 $ra
			move $s7 $s1
			jal last
			move $s5 $s7
			move $s7 $s2
			jal last
			move $s6 $s7
			lw $t5 0($s5)
			lw $t6 0($s6)
			li $s0 0x10040080
			sub $s3 $s7 $s2
			add $s3 $s3 8
ploop:		beq $s3 $zero pend
			add $t0 $t5 $t6
			sub $s0 $s0 4
			sub $s6 $s6 4
			sub $s5 $s5 4
			sub $s3 $s3 4
			lw $t5 0($s5)
			lw $t6 0($s6)
			bge $t0 10 carry
save:		sw $t0 0($s0)
			j ploop
pend:		beq $t0 0 null
endnull:	move $ra $a3
			jr $ra

null:		add $s0 $s0 4
			j endnull

carry:	    sub $t0 $t0 10
			add $t5 $t5 1
			j save


last: 		lb $t7 0($s7)
lloop:		beq $zero $t7 testnext	
weiter:		add $s7 $s7 4
			lw $t7 0($s7)
			j lloop
lend:		sub $s7 $s7 4
			lb $t7 0($s7)
			move $t9 $s7
			jr $ra
testnext:	add $s7 $s7 4
			lw $t7 0($s7)
			bne $t7 $zero kleiner10
			sub $s7 $s7 4
			j lend
kleiner10: 	blt $t7 10 weiter
			sub $s7 $s7 4
			j lend

Da es bei Assembler nicht einfach revert(x) gibt. Werden die Zahlen von Anfang an in einen Array gespeichert... Dementsprechend musste ich meine eigene Additionsfunktion schreiben...

Hello World hat geschrieben:

e1bart0 hat geschrieben:

Dann werfe ich auch mal meine Lösung in die Runde: http://paste.pocoo.org/show/31710

Diese Lösung ist aber IMHO nicht korrekt. Meine Lösung, die Java-Lösung und audax' Python-Lösung spucken 6091 Zahlen aus, Deine dagegen 7444.

Hm, bei reverse rundet er komischerweise (eigentlich sollte er das wegen Math::GMP nicht tun), deswegen kann ich nicht prüfen, ob die Zahl ein Palindrom ist... Hier eine Lösung mit Math::BigInt; gibt auch 6091 Zahlen aus, ist aber verdammt langsam: http://paste.pocoo.org/show/31891/

so....dann hab ich meine ruby lösung mal berichtigt (und auch im Wiki nachgebessert):

def reverse zahl
  zahl.to_s.reverse.to_i
end

def is_lychrel n, tries=100
  rev = reverse n
  1.upto(tries) {
    n += rev
    rev = reverse n
    return false if n == rev
  }
  true
end

1.upto(ARGV[0] ? ARGV[0].to_i : 100000) { |i|
  print i, " könnte eine Lychrel-Zahl sein\n" if is_lychrel i
} 

Hallo zusammen,
hier meine Fortran-Lösung. Leider auch nur mit 20 Durchläufen pro Zahl.

program Lychrel_Zahl
  implicit none 
  
  integer, parameter :: lang = selected_int_kind(16)
  integer(kind=lang) :: z1, z2
  integer            :: i, z, n=0
    
  do z=100000,0,-1
     z1  = z    
     do i=0,25
        call reverse(z1, z2)
        z1 = z1 + z2
        call reverse(z1, z2)
        if (z1 == z2) exit
        if (i  == 25) print*, z 
     enddo    
  enddo 

end program

subroutine reverse(z1, z2)
  implicit none

  integer, parameter :: lang = selected_int_kind(16) 
  integer(kind=lang), intent(in)  :: z1
  integer(kind=lang), intent(out) :: z2
  integer(kind=lang) :: zahl
  integer            :: hilf

  z2   = 0
  zahl = z1

  do
     hilf =  modulo(zahl,10)
     zahl = (zahl-hilf)/10 
     z2   = 10 * z2 + hilf 
     if (zahl == 0) exit
  enddo

  return

end subroutine

Grüße
Gerrit

@audax: Ja die globalen Variablen sind nicht so schön. Für den PC wäre es kein Problem die lokal zu den Funktionen zu deklarieren und Zeiger zu übergeben, aber beim C64 ist so eine Indirektion richtig übel. Wenn das Feld global ist, bekommt man die 16-Bit-Adresse wie folgt in die beiden 8-Bit-Register A und X:

        lda #<foo
        ldx #>foo

Wenn man indirekt über einen Zeiger gehen muss, der auf dem Stack liegt, also auch wieder indirekt über einen Zeiger addressiert werden muss, dann sieht das so aus:

        ldy #0
        lda (sp),y
        sta ptr1
        iny
        lda (sp),y
        sta ptr1+1
        lda (ptr1),y
        tax
        dey
        lda (ptr1),y

Die erste Variante dauert 4 Taktzyklen, die zweite 34 bis 36 Taktzyklen. Das wäre also deutlich langsamer.

An die ganzen 20-Iterationen-Menschen: Seid doch nicht so faul und implementiert einen eigenen Datentyp für die ganzen Zahlen. Es ist doch wirklich nur "reverse" und Addition gefragt. Das ist Mathematik auf Grundschul-Niveau. ☺

Marc 'BlackJack' Rintsch hat geschrieben:

An die ganzen 20-Iterationen-Menschen: Seid doch nicht so faul und implementiert einen eigenen Datentyp für die ganzen Zahlen. Es ist doch wirklich nur "reverse" und Addition gefragt. Das ist Mathematik auf Grundschul-Niveau. ☺

Hab ich doch schon, werde das ganze dann nachher mal mit 100 Iterationen in c++ und mit meiner tollen bignum-Klasse, auf die ich immernoch sehr stolz bin 😀

Marc 'BlackJack' Rintsch hat geschrieben:

An die ganzen 20-Iterationen-Menschen: Seid doch nicht so faul und implementiert einen eigenen Datentyp für die ganzen Zahlen. Es ist doch wirklich nur "reverse" und Addition gefragt. Das ist Mathematik auf Grundschul-Niveau. ☺

Mein Problem ist nicht die Mathematik: http://forum.ubuntuusers.de/topic/157429/ .

Marc 'BlackJack' Rintsch hat geschrieben:

Und eine C-Lösung. Ist nicht besonders hübsch, da auf Geschwindigkeit getrimmt: Test der Zahlen 1 bis 10000 dauert auf dem C64 damit nur 14 Minuten. ☺

Welchen Compiler benutzt du auf dem C64? cc65? Power-C?
mal sehen ob ich noich nde 6502-Assembler-Variante hinbekomme und ob die < 10 min. läuft 😉