Bitkostnad, divisionsalgorithm: varför tänker man att aritmetiken alltid görs med n-bitarstal?
Hej, vet inte om "Matematik>Övrigt" är rätt forum för det här, upplys mig om jag har fel. Sitter med nedanstående uppgift, som jag har ringat in en rad på (läs vidare så förstår du varför)
(kommentar: där jag ringade in blev det kanske lite svårläst: a' <- a' + a står det på den raden, q' <- q' +1 i den raden under.)
Facit säger
Man säger att "alla aritmetik görs med n-bitarstal" i facit (vilket jag också markerat).
Men, på raden i uppgiftsbeskrivningen som jag markerade står det a' <- a' + a. a' = 0 från början. Hur kan vi vara så säkra på att a' <- a' + a fortfarande är en addition mellan n bitar, om loopen kört ett par gånger? Eller är det bara en förenkling man gör att anta det?
Följer det av att resten inte kan ha fler bitar än nämnaren, vid en division?
Bubo skrev:Följer det av att resten inte kan ha fler bitar än nämnaren, vid en division?
Jag förstår inte riktigt vad du menar tyvärr. Det jag tänker är att när vi har raden a' <- a' + a, alltså att vi adderar nämnaren till sig själv, vad säger oss att t.ex. , , osv. fortfarande kommer vara ett -bitartal?
Raden a' <- a' + a står innanför en while-slinga som körs under villkoret att a' + a ≤ r. Själva resten är mindre än a, så om n bitar räcker för a, så räcker de även för r och därmed även för a'+a.
Just ja, tack så mycket! Nu förstår jag.
