Sida 2 av 2

Re: Dela snabbt med 2

Postat: 27 juni 2025, 16:04:22
av 4kTRB
Smart.

Re: Dela snabbt med 2

Postat: 27 juni 2025, 17:04:59
av E Kafeman
guckrum skrev: 27 juni 2025, 10:47:51 Kan du omvandla till talbas 3 utan att utföra divisioner med 3? "Itererande binär bitskiftning", avser det den vanliga divisionsalgoritmen, eller vilken metod tänker du på?
Omvandling till talbas 3 kan ske lite olika vägar beroende på vilken talbas man utgår från och vilken precision man vill ha, integer eller flyttal samt om man kan nöja sej med att utföra operationen en gång per värde. Skapar man den som indexerad tabell kan man göra det mycket enklare vid tabell-skapandet genom att upprepa ett enkelt mönster i vertikalled för varje delsiffra:
000
001
002
010
011
....
Decimala värdet 4 omvandlas i den matteintesiva efterföljande programkoden till talbasen 3 genom att peka i tabellen: 010[4].

Binär iterering för att dividera flyttal med tre genom bitskiftning fås av 1/3 = 1/4 + 1/16 + 1/64 + ...
Gissar att det är den algoritmen du syftar på?

Decimala integers kan också divideras med tre genom att skapa en indexerad tabell:
[0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4 ....]
Vill man dividera decimala talet 12 med tre ges svaret vid index [12].
Vinsten är att indexering kostar minimalt med CPU-jobb. Beroende på typ av matematisk operation kan man ofta nöja sej med att endast lägga in rätt index i en pekare utan att konkret kopiera in pekade värdet i något minne och slipper utföra någon matematisk operation i detta programsteg.

Talbaser, ibland hanteras de bakom ryggen på den som skriver programkod i kompilatorn på lite högre nivå av programmering men för assembler eller än lägre, direkt maskinkod är det vanligast med hexadecimal tal-representation och som huvudsaklig talbas.
Andra talbaser är normalt mindre cpu-optimala mot hur de flesta processorer jobbar om det är en 8, 16, 32, 64.. bits aritmetisk bredd på processorn.

Vad som är processor-optimerat enligt ovan är inte alltid sant.
Är det en mer avancerad processor, typ 80286 så kan det finnas flyttalsdel som tillägg antingen direkt i processorn eller som extra hårdvara, 80287, samt intern cache, multitrådning och mantissa-hantering som gör att det blir en ny dimension för att skriva optimal assembler-kod för komplexa matematiska operationer. Att bygga indexerade tabeller eller låta flyttals-motorn sköta jobbet kan bli en avvägnings-fråga.
Om hårdvaran för flyttal finns kan det vara mer tids-lönsamt att nyttja den för att snabbast utföra en komplex matematisk operation.

Cache-delen kan ställa till det med optimeringen då en matematiska operation kan gå snabbare vid repetition, när samma operation utförs en andra gång. Då kan det löna sej att låta enkla sekvenser repeteras för att utföra en matematisk process än att för samma slutresultat göra mer komplex följd av cpu-operationer.

Bara för att nämna udda processor där ovan matematik inte alltid är optimal eller ens möjlig är Motorolas MC14500B.
Det är en en-bits-processor utan dedicerad programräknare eller indexpekare för minnet vilket gör dynamiskt skapande av indexerade tabeller i minnet lite mer komplicerat. https://en.wikipedia.org/wiki/Motorola_MC14500B

Re: Dela snabbt med 2

Postat: 29 juni 2025, 00:54:12
av adent
Min första tanke var förstås:

a = b >> 1;

:)

Re: Dela snabbt med 2

Postat: 29 juni 2025, 08:12:01
av E Kafeman
Du menar du tänkte så här
binärt
0001 = 0011 >>1
eller decimalt
58 = 587>>1

Integern 587 är ett primtal, liksom talet 3 här ovan. Då spelar det ingen roll vilken talbas man väljer att högerskifta ett steg så blir det alltid en rest som måste hanteras om man ska få korrekt resultat vid division med en integer.
Decimala udda tal som inte är primtal kan däremot högerskiftas utan att man får en rest i minst en talbas.

Som exempel, decimala och udda talet 9 är inte ett primtal vilket garanterar att det finns en talbas där man kan högerskifta utan att få en rest.
9[d] kan skrivas som 100[3] vilket kan högerskiftas till 10[3] vilket kan skrivas som 3[d]. Högerskift ett steg i talbasen 3 ger alltid division med 3.

Vet inte om TS val av primtal var medvetet val men det visar på problemet med att allt för enkel matematik inte alltid fungerar och primtal ställer ofta till det när man söker optimalt snabb och simpel matematiska lösning både som huvudräkning och programmeringsmässigt.

Om man vill ha optimalt snabb datorprocessande typ division eller multiplikation kan man programmeringsmässigt värdera decimala tal efter dess första siffra och baserat på det välja att hoppa till en enklare integer-beräkning eller till en mer processorkrävande lösning.

Ett sätt som jag tidigare visade hur man hanterar primtal var att tillfälligt lägga till en nolla så talet blir 5870 som inte är ett primtal. Det talet går utmärkt att halvera genom att högerskifta ett steg binärt.
Att lägga till en nolla i decimala systemet, dvs multiplicera med 10, kan skrivas som:

a = b << 1;

Re: Dela snabbt med 2

Postat: 29 juni 2025, 12:42:18
av 4kTRB
Nej det var inte menat mer än vad jag faktiskt mätte plankan till och tog det som exempel. Inte en tanke på att det råkade vara ett primtal. En primtalsplanka råkade det vara alltså :)

Re: Dela snabbt med 2

Postat: 29 juni 2025, 19:42:22
av guckrum
Binär iterering för att dividera flyttal med tre genom bitskiftning fås av 1/3 = 1/4 + 1/16 + 1/64 + ... Gissar att det är den algoritmen du syftar på?
Ja, det där är ett bra exempel. Det jag ville komma till är att man kommer inte runt divisionalgoritmen (typ "trappan" eller "liggande stolen" som man lärde sig i grundskolan) utom i enkla specialfall. (Nu tänker jag att vi inte beaktar tabeller eller specialapplikationer och akademiska saker som abelska grupper, kroppar, ringar, fouriertransformer, funktionsapproximationer osv).

Vi har två fall för division:

1. Både täljare och nämnare är okända. Till exempel får jag plötsligt till uppgift att dividera 123 med 456. Då måste jag plocka fram divisionsalgoritmen och utföra divisionen steg för steg, med början från den mest signifikanta siffran i täljaren och jobba mig "neråt" ett steg i taget.

2. Nämnaren är känd i förväg, till exempel som en konstant i ett program. Om jag vet att någon strax kommer att be mig dela ett tal med tre kan jag under tiden förbereda lite. Till exempel kan jag använda divisionalgoritmen för att ta reda på vad 1/3 är i förväg, och sedan multiplicera det med talet jag skall dividera. I fallet med 3 är ju 1/3 är 0.333...(10) eller 0.01010101...(2). Den senare är upphovet till 1/4 + 1/16 + 1/64 + ... ovan.

Att göra om division till multiplikation med invers är smart, för multiplikation är mycket enkare att utföra än division. Att multiplicera är att skapa och sedan addera ihop så kallade partialprodukter (och man kan göra detta i valfri ordning eller rentav parallellt). En variant av detta är det som händer när vi implementerar "shift and add". För 1/3 i binär form så skiftar man täljaren två steg åt höger, adderar till resultatet, och upprepar till man har den upplösning man behöver.

Re: Dela snabbt med 2

Postat: 30 juni 2025, 10:59:16
av E Kafeman
> 0.01010101...(2). Den senare är upphovet till 1/4 + 1/16 + 1/64

Det är snarare en del av samma kalkyl visad i olika talbaser. Sådana tal-serier liksom för division med tre och andra siffror har existerat mycket länge och troligen kom de först i decimal form. Archimedes använde sådana serier kring 200 BC bl.a för att beräkna area i en sekantbegränsad parabelyta.
Sådan talserier användes säkert till mycket annat än parabler men det är exempel som Archimedes själv skrivit om.

De flesta ser nog inte tabeller som "enkla specialfall" eller något av akademisk betydelse utan tvärs om många gånger överlägsen metod att beräkna komplexa matematiska funktioner både som integer och som flyttal.
Enkla snabba men energisnåla processorer där man vill beräkna olinjära komplexa funktioner med minsta fördröjning i dynamiska reglersystem med låg processorkraft i nära realtid, där lämpar sej ofta tabell-baserade beräkningar.
Kan vara att t.ex. att styra roder på en projektil eller förse en kamera med elektriskt styrd autofokus, zoom, antiskak-funktion mm.

Tabellserier behöver inte vara utrymmeskrävande. Exempelvis för decimala tal räcker det om man täcker 0-9 för en viss funktion och och sedan kan ofta valfritt stort tal byggas upp.
Vill man använda en sinusfunktion räcker det med värden för den första kvadranten, övriga värden kan utläsas genom att välja subrutin för resp kvadrant.

Tabeller är simpelt att implementera även i rätt enkla processorer och just för att detta är enkel och effektiv metod att arbeta med sådan förskapade tabeller har det varit använt tusentals år tillbaka även när huvudräkning var det som var processorn.

Räknestickan är ett bra exempel på användandet av olinjära kurvor för att utföra komplexa beräkningar med minimalt med processande. Tabellerna är utskrivna direkt på räknestickan med skalenliga relativa proportioner till linjära talserier.
Liksom för analog-datorn (analogi-maskinen) kunde man använda logaritm-kurvor för både division och multiplikation.
Räknestickan var något som man förr alltid hade inom räckhåll på skrivbordet och som man använde vid de flesta beräkningar.
räknesticka.jpg
En avancerat räknesticka kan ha många olika skalor på bägge sidor för olika typer av beräkningar och den skjutbara stickan i mitten kan man ofta dra ut och vända på för ytterligare några skalor och nya funktioner.
Finns även cirkelrunda och cylindriska motsvarande räknestickor som används än idag. Försedda med skalor för specifikt ändamål är de snabbare än en fickräknare och för ändamålet ofta tillräckligt exakta med ca 3 värdesiffror. Lär vara standard verktyg för piloter av passagerarplan med räknesticka för navigations-beräkningar som fungerar när alla elektriska apparater givit upp. Kan se ut så här:
Navigation_ruler.png
Många tekniker har nog fortfarande Tefyma eller Elfyma-boken inom räckhåll. Den innehåller alla de viktigare tabellerna så att man ska kunna utföra beräkningar för hand utan hjälp av något elektriskt eller ens en räknesticka.

Mekaniska räkneapparater såsom Facit och Addo är däremot endast linjära i sin mekanik och mer ett verktyg för lönekontoret.

Ett antal op med valbara olinjära förstärkningkurvor kan användas för liknande beräkningar. Kallades analog-maskin. Olinjära kurvor skapades med en serie RC-kretsar med och motkopplade istället för att skapa med tabeller.

Analog-maskinen var under 50-80-talet vanlig inom många processer inom industrin. Iofs inte så pedagogisk och komplex som denna som var vanlig för utbildning i skolvärlden:
Analog_dator.png
Som kuriosa, en programmerbar analog-beräknare jag stött på i jobbet var helt mekanisk med utbytbara kammar och kugghjul i olika profiler. Indata till denna avancerade bakmaskinen för olika kemikalier var bl.a flödes, nivå, rotations-givare tryck och temperatur-givare. Utdata levererades som reostatvärden som återkopplade till DC-motorer och värmeelement.
Reostaterna justerades mha av pendlar som kunde flytta reostatpådraget stegvis ett steg upp eller ner lite som en centrifugal-regulator fast i bägge riktningarna.
Denna analoga strömlösa beräkningsmaskin stor som en garderob var toppmodern när den installerades 1955.

Vid samma tid fanns kalkylerande strömlösa flygplans bomb-sikten som tog in en massa data om flygplanet position och höjd, omgivningens vind och temperatur samt bombens glidegenskaper. Om man försett bombsiktet med rätt data så kunde precisionen bli god.
På motsvarande sätt fanns för luftvärnet sk. riktmedel som var elektriska. I Sverige använde vi ett riktmedel som invändigt var försett med många kamkurvor hävarmar, variabla växellådor och som drevs av drygt 40 små elmotorer.
Log-beräkningar var enkelt fixade i dessa maskiner. Kunde se ut så här:
log_calc.png
Alla andra vanliga beräkningar mha sin arctan, ln. x³ finns som färdiga mekaniska lösningar.

Tabellverk för olika beräkningar för t.ex. sjö-navigering efter stjärnor har funnits mycket länge men stora genomslaget för allmänt tekniskt bruk av räknestickor som ersättning av tabellverk startade med att en engelsk matematiker skapade tabeller för log-skalan för att kunna ersätta divisioner och multiplikationer med enklare addition och subtraktioner. Det skedde i början på 1600-talet. 1632 anges som födelseåret för den moderna räknestickan. Var rena trolleriverktyget där man kunde utföra komplicerade divisioner och multiplikationer på några sekunder.
Även seriell matte såsom "ln5 x sin45 / log2" är enkel att utföra på räknestickan. Ställer man in värden väl så ges resultatet med 3 värdesiffror vilket ofta är fullt tillräckligt.
Forna tidees tekniker fick dock själva hålla reda på nollorna och exponenterna fram till att de första handhållna miniräknarna med inbyggd exponent.
Allt fick man inte helt serverat i början som färdiga funktioner.
Många funktioner som fanns på räknestickan fanns inte men referenser skrevs direkt på Sinclair-räknarens ovansida.
Den räknaren kom ca 1977 och var nog den första mer avancerade räknaren som inte kostade mer än en bättre räknesticka.
Den såldes även som byggsats. Drevs med ej laddbara batterier och tog en gel del ström, så det var fortfarande bra att ha räknestickan till hands när batterierna tog slut.
Sinclair_scientific.png
Notera hjälpsiffrorna som är skrivna på räknaren. För mer komplicerad trigonometri fanns även en lapp medskickad med räknaren som visade hur man kunde kombinera knapp-tryckningar för nya trigonometriska funktioner. Den lappen var självklistrande och passade inuti höljet till räknaren.
Den första produkt jag tog fram var ett laddbart paket till just denna miniräknaren.

MSB vill att vi ska hålla oss med ficklampor och radio med inbyggd vevgenerator för att vi ska klara oss vid en större samhällskris. När en sådan kris kommer, såsom den väntade stora solstormen som då slår ut all el och datorer dör även transistorerna i radion. Gör inget då även sändaranläggningarna blir utslagna, så det finns inget att lyssna på.
Det kommer behövas mängder med tekniker som kan utföra beräkningar vid återbyggnaden av samhället efter en sådan händelse och de behöver då kunna göra komplicerade beräkningar utan el.
Det är dock inga bekymmer, räknestickan och Tefymans tabeller fungerar fortfarande.

Re: Dela snabbt med 2

Postat: 30 juni 2025, 13:35:21
av guckrum
De flesta ser nog inte tabeller som "enkla specialfall" eller något av akademisk betydelse utan tvärs om många gånger överlägsen metod att beräkna komplexa matematiska funktioner både som integer och som flyttal.
Enkla snabba men energisnåla processorer där man vill beräkna olinjära komplexa funktioner med minsta fördröjning i dynamiska reglersystem med låg processorkraft i nära realtid, där lämpar sej ofta tabell-baserade beräkningar.
Naturligtvis är det så från det användarperspektivet. Det fungerar bra där det fungerar bra. Men om man ser det från perspektivet från den som bygger kretsar för hög prestanda ser det helt annorlunda ut. Gränsen mellan vad som är tabell och vad som är aritmetik är flytande, då dedikerat ROM är otänkbart för små tabeller, och oavsett har dålig bandbredd om det är större, och allt istället måste realiseras med grindar. Och ju fler man har, desto långsammare går det. Så där är det annorlunda. Om man väljer det perspektivet alltså.

Jag gjorde distinktionen för att hålla diskussionen på kurs för att inte slinka ner i diket och diskutera hur vanligt det är med hårdvara som konverterar mellan talbaser eller varför inte räkna i Galoaskroppar där allt är annorlunda eller varför man helt enkelt inte gör världens största tabell med alla möjliga beräkningar förutberäknade. Man kan ju tabulera allt. Men faktum är att någon måste generera tabellen, och då måste man dividera, och tråden handlade lite om division, tyckte jag. Beroende på applikation och krav så finns det en balans mellan det man behöver räkna ut i stunden och det man kan ha förberett i god tid innan.

Re: Dela snabbt med 2

Postat: 30 juni 2025, 16:15:51
av Nerre
Om vi går tillbaka till ursprungsfrågan (att dela med 2), så är ju vi människor bra på att känna igen "mönster". Vi kan relativt snabbt se på ett tal om det är jämnt och om det är enkelt att dela med två. Men det är väl just såna där specialfall.

Re: Dela snabbt med 2

Postat: 1 juli 2025, 09:35:23
av E Kafeman
>gör världens största tabell med alla möjliga beräkningar
Det är i detta sammanhang inte särskilt smart, sådana dataprogram fallerar att utföra små snabba optimerade beräkningar och blir sämre på att utföra sin funktion och slösar med hård och mjukvara.
Inga processer som gör anspråk på att vara optimerade på att utföra något har någon nytta av "världens största tabell".
Tvärtom behöver tabellen vara nedskalad från allt som inte kommer nyttjas.
Optimerat effektivt exekverande av dataprogrammet kräver att den som skriver datorprogrammet förstår vad som är effektivt i sammanhanget.

Ett enkelt exempel är om man med MCU vill hålla räkning på vilka spelkort som passerat i kortleken när man spelar black jack. Blir man påkommen blir man utkastad från kasinon, då det räknas som fusk.
Tillräckligt liten MCU kanske inte upptäcks eller man kanske kan hacka programkoden i armbandsklockan till att omärkligt signalera när det är dags att storsatsa. Tillräckligt litet program kan kanske trängas in i existerande programutrymme.
Då behövs en tabell med 52 binära positioner per kortlek (lite mindre än 8 hex-bytes totalt minne).
Större eller fler tabeller har ingen relevant funktion. Det är en optimerad tabellstorlek för att skapa mest utbyte av utrymme och programkods effektivitet.

Detta med att skala ned funktion till dess kärnbehov och inte ta med ej använda funktioner är på samma sätt vi jobbar bäst vid huvudräkning. De tabeller vi letar efter i huvudet är de som behövs för stunden. Ska vi multiplicera en mängd heltal med 6 försöker vi minnas dess tabell som ett uppslag och utantilläxa som inte behöver beräknas varje gång vi plockar fram tabellen i huvudet.
Vi bryr oss då inte heller om att ta reda på om 7:ans multiplikationstabell finns kvar i något skrymsle av hjärnan. Det skulle bara distrahera med onödiga tabeller.

> varför inte räkna i Galoaskroppar där allt är annorlunda
Du menar mattematikern Galois och hans teori?
Han hade ingen egen algebraisk kroppsdefinition, eller är det någon annan du tänkte på? Vad skulle då vara annorlunda?
"Galois grupper" är kanske vad du tänkte på i stället för kroppar?
Det är i vart fall en bit från hur man delar en planka i ett antal lika långa delar på ett smart sätt.
Dela vid nollställen för polynomet kanske?

Detta att känna igen mönster är det som till stor del ger oss snabb förmåga att lösa tal-problem vid huvudräkning.
Bland de mönster man brukar få lära sej tidigt är multiplikationstabellen. Man lär sej mönster för utvecklingen i tabeller från 1 till 12 . Vi vet vad 7x7 eller 12x12 är utan att egentligen räkna utan vi slår upp det i våra inlärda tabeller.
Omvänt, divisionstabelller, fastän de kan utgöras av samma utantill-lärda tabeller har många svårare för det.
Om något går dela med två utan rest är enkelt, vi lär oss att talet måste sluta på en jämn siffra och det är bara första siffran oavsett hur stort talet är som vi måste kolla i intervallet 0-9. Slutar talet på siffran 0 eller 5 vet vi ofta att en mängd andra kortvägar inom matematiken är möjlig.
Råkar vi ut för matematiska problem utanför våra inlärda tabeller och mönster får vi det genast mycket svårare om vi verkligen måste räkna. Redan enkla additioner och många måste börja räkna fingrar vilket gör att beräkningar tar mycket längre tid. När fingrarna inte räcker till får vi börja skriva ned på papper de olika seriella delberäkningarna för att kunna göra korrekta totala beräkningar.

För att kunna göra dessa seriella beräkningar har vi förutom utantill-tabeller ofta utantill-lärda metoder för de fyra räknesättet, hur man kan ställa upp tal och delberäkna dom för enklare siffror innan man gör en slutlig summering av deltalen.

På motsvarande sätt kan vi använda mönsterigenkännande för att lösa problem där vi inte har färdiga tabeller.

1x11 = 11
2x11 = 22
3x11 = 33
4x11 = ??

Med ovan tabell har vi inga problem att skriva in rätt svar på sista steget utan att beräkna något utan tillämpar bara fortsättningen på ett mönster.

Det är dock ingen helt säker metod. Mönstret kan förändras och och svaren på beräkningarna blir mer komplexa för större multiplikanter om vi fortsätter på 11:ans tabell:

11x11 = 121
12x11 = 132
13x11 = 143
14x11 = ???

Å andra sidan så ser vi redan efter att ha lärt oss acceptera de första svaren att det nu finns nya mönster som gör att 14x11 kanske kan lösas med mönsterigenkänning genom att se på sifferföljder i tidigare tal.
Vi kan se sifferföljds-mönstret vertikalt men det är lite smartare att se mönstret horisontalt då det låter oss utveckla det till betydligt större tal utan att återskapa tabellen.
I detta fallet tar vi summan av talen i siffran 14 (1+4 = 5) och sätter den siffran mellan 1 och 4 så det blir 154 som svar på multiplikationen.
53x11 är således 583 och kräver minimalt med tanke för att beräkna om man kan mönstret.
Alla multiplikationstabeller har ett mönster där det kan krävas enklare beräkning men man slipper summera större tal i huvudet om man ser mönstret.

Ett sådant exempel är 85x 85 eller 85². Här är knepet att lägga till ett på en av tiotalsiffrorna och därefter multiplicera entalssiffrorna.
(1+8)x8= 72xx
     5x5 = xx25
Summa   7225

Det är ett återkommande mönster som återkommer typ 45² => 5x4=20xx => 45²=2025
Det är enkelt att beräkna sådana tal i huvudet.
Alternativ finns multiplikations-metoder som gör att man inte behöver hålla reda på några större delsummor.
45² kan även beräknas så här:
45x45 => 4x4=16xx (4x5+4x5)=x40x 5x5=xx25

 16xx
 x40x
+xx25
=2025

I huvudet går sekvensen så här:
23x41=>
 8xx
 14x
 xx3
=943

Alternativt så förenklar man 23x41 till enklare multiplikatorer.
Siffrorna 0,2,4 och 5 är ofta enklare att räkna med än andra siffror.

23x40=92x ; Enklare då 4 beräknas som två dubblingar.
23x1 = x23 ; Resten
        = 943 ; Summa

Det kan säkert vara individuellt vad man tycker är enklare beräkningsalternativ vid huvudräkning beroende på hur man är van att räkna.
Programmerar man mycket lågnivå kan man t.o.m. vänja sej vid att se hexadecimala och binära tal som enklare att räkna med än decimala tal.
Det är oavsett förhållandevis långsamma sätt att räkna som beskrivits här ovan, med eller utan hjälpmedel.
Bor man i Japan kan man räkna på något betydligt snabbar redskap, en Soroban.
Ännu snabbare när man använder det virtuellt.

Någon som törs tävla mot småbarnen i huvudräkning eller utmana dom mha miniräknare?