Seite 1 von 1
Multiplikation
Verfasst: Donnerstag 11. April 2013, 12:40
von fail
Multiplikationsalgorithmus ohne * oder module zu benutzen.
Funktioniert für [-999999,.....,-2,-1,0,1,2,.......,999999]
Code: Alles auswählen
def multiplication(a,b):
if b>=0:
return sum(a for _ in range(b))
elif a<0 and b<0:
return sum(-a for _ in range(-b))
else:
return sum(b for _ in range(a))
Re: Multiplikation
Verfasst: Donnerstag 11. April 2013, 12:49
von EyDu
Du hast im Prinzip drei identische Zeilen, welche jeweils die Summe bilden. Daher solltest du diese aus den if/elif/else-Blöcken rausziehen und darin nur die Dinge behandeln, welche tatsächlich unterschiedlich sind.
Auch, wenn es sich hier nur um Spielerei handelt: probiere mal ``multiplication(1, 1000000000)`` und ``multiplication(1000000000, 1)`` aus und überlege dir, warum sich die Aufrufe unterschiedlich verhalten.
fail hat geschrieben:Funktioniert für [-999999,.....,-2,-1,0,1,2,.......,999999]
Was willst du damit sagen? Dass es für alle ganzen Zahlen funktioniert?
Re: Multiplikation
Verfasst: Donnerstag 11. April 2013, 13:12
von fail
Ja, es funktioniert nur für ganze zahlen.
Meinst du das die kleinere Zahl im range() sein sollte?
Re: Multiplikation
Verfasst: Freitag 12. April 2013, 09:59
von EyDu
fail hat geschrieben:Meinst du das die kleinere Zahl im range() sein sollte?
Ja, das wäre geschickter. Aber das Beispiel ist ja eh nur akademischer Natur.
Re: Multiplikation
Verfasst: Freitag 12. April 2013, 15:00
von BlackJack
@fail: Es gibt übrigens noch eine effizientere Methode die mit Bit-Verschiebungen und Addition auskommt. Also die Operatoren ``<<``, ``>>``, und ``+``.
Re: Multiplikation
Verfasst: Freitag 12. April 2013, 16:08
von fail
Re: Multiplikation
Verfasst: Freitag 12. April 2013, 18:08
von EyDu
Nein, das ist eine nichtfunktionierende Lösung (b=0). Davon abgesehen handelst du dir natürlich die üblichen Probleme mit floats ein.
Re: Multiplikation
Verfasst: Samstag 13. April 2013, 11:51
von jerch
BlackJack hat geschrieben:@fail: Es gibt übrigens noch eine effizientere Methode die mit Bit-Verschiebungen und Addition auskommt. Also die Operatoren ``<<``, ``>>``, und ``+``.
Als Fingerübung kann man auch gleich die Addition mittels Bitoperatoren mit umsetzen. Interessant dürften da AND (&) und XOR (^) sein.
Re: Multiplikation
Verfasst: Sonntag 14. April 2013, 16:50
von fail
Ich schaff die addition einfach nicht. Ich hab schon alles versucht. Der Fehler ist wahrscheinlich in der Addition funktion, aber ich kann ihn nicht finden.
Code: Alles auswählen
from functools import reduce
def addition(a,b):
a = list(map(int,list(bin(a)[2:])))
b = list(map(int,list(bin(b)[2:])))
remainder = 0
resultat=[]
for c in reversed(range(max(len(a),len(b)))):
resultat.append(adder(get(a,c),get(b,c),remainder)[0])
remainder=adder(get(a,c),get(b,c),remainder)[1]
return bin2dec(list(reversed(resultat)))
def adder(a,b,cin):
s=cin ^ a ^ b
cout=(a&b)| (cin&(a^b))
return s,cout
def get(von,das):
try:
return von[das]
except IndexError:
return 0
def bin2dec(binary):
return reduce(lambda acc,y: acc*2 + y,binary)
Re: Multiplikation
Verfasst: Sonntag 14. April 2013, 17:20
von BlackJack
@fail: Ich würde es ja nicht mit einzelnen Bits in einer Liste machen sondern mit den Zahlen und den Bitoperationen selbst, denn die werden intern ja schon binär gespeichert.
Edit:
Code: Alles auswählen
def add(a, b):
while True:
a, b = a ^ b, b & a
if b == 0:
return a
b <<= 1
Re: Multiplikation
Verfasst: Sonntag 14. April 2013, 17:40
von jerch
@fail:
Das ist viel zu kompliziert gedacht. Schau Dir mal einen Halbaddierer an. Das kann man gut übertragen.
Edit:
Kleine Ergänzung, um den Überlauf für bestimmte Vorzeichensituationen loszuwerden:
Code: Alles auswählen
def add(a, b):
if a == -b:
return 0
if a < b:
a, b = b, a
if a > 0 and b < 0:
if -b < a:
return -add(-a, -b)
while True:
a, b = a ^ b, b & a
if b == 0:
return a
b <<= 1
Re: Multiplikation
Verfasst: Montag 15. April 2013, 11:53
von nomnom
@jerch: Du benutzt doch in deinem Code ständig "-", das ist doch unfair :p Dann geht auch
Re: Multiplikation
Verfasst: Montag 15. April 2013, 21:07
von derdon
Die Klammern sind überflüssig:
Re: Multiplikation
Verfasst: Montag 15. April 2013, 21:42
von nomnom
derdon hat geschrieben:Die Klammern sind überflüssig:
Und woher soll Python dann wissen, ob nicht (a-)-b gemeint war????
Re: Multiplikation
Verfasst: Montag 15. April 2013, 21:54
von BlackJack
@nomnom: Öhm, das wäre ein `SyntaxError`:
Code: Alles auswählen
n [86]: (a-)-b
File "<ipython-input-86-e4fa2a309856>", line 1
(a-)-b
^
SyntaxError: invalid syntax
Re: Multiplikation
Verfasst: Montag 15. April 2013, 22:28
von jerch
nomnom hat geschrieben:@jerch: Du benutzt doch in deinem Code ständig "-", das ist doch unfair :p Dann geht auch
Ok, Abkürzungen gelten nicht:
Code: Alles auswählen
ZERO = 0
ONE = 1
# simple 1 testing
def is_one(a):
return ONE if a==ONE else ZERO
# xor equal testing
def equal(a, b):
return is_one(((a^b) << ONE) | ONE)
# testing for zero (lazy version with using equal)
def is_zero(a):
return equal(a, ZERO)
# simple incrementor
def inc(a):
if equal(a, ~ZERO):
return ZERO
b = ONE
while ONE:
if is_zero(b):
return a
a, b = a^b, (a&b) << ONE
# negativate number: positive to negative and negative to positive
def neg(a):
if is_zero(a):
return a
return inc(~a)
Jetzt kannst Du das '-' mit neg() ersetzen. Damit kannst Du die komplette Intergerarithmetik auf Bitoperatoren und den basalen 1 oder 0 Test zurückführen. Hochintegrierte ALUs waren gestern, hoch leben die Register
(Zur Anschaulichkeit hab ich 1 und 0 mal durch "Konstanten" ersetzt)