Vi presenterar en generisk siffra seriell metod (DSM) för att beräkna siffrorna i ett reellt nummer V. Bounds på dessa siffror, och på felen i de tillhörande uppskattningar av V bildas från dessa siffror, härleds. För att illustrera våra resultat, vi härleda sådana gränser för en parameteriserad familj av high-radix algoritmer för division och kvadratrot. Dessa gränser gör det möjligt för en DSM-designer att bestämma, till exempel, om ett givet val av parametrar tillåter snabb bildning och avrundning av dess approximation till V. Index Terms-Digit seriell metod, siffra upprepningsmetod, mixed-radix representation, on-the-fly teknik, high-radix, division, kvadratrot, siffergränser, felgränser Ç LET V vara ett verkligt tal. En siffra seriell metod (DSM) är en algoritm som bestämmer siffrorna i V seriellt, börjar med den ledande siffran. En DSM börjar med att initiera en ackumulator till noll och, som varje siffra bestäms, den siffran är anpassad och läggs till ackumulatorn. Successiva värden av denna ackumulator bildar en sekvens av uppskattningar av V. Det primära bidraget av detta papper är en generisk DSM-analysmetod för att bestämma gränser på magnituderna av siffrorna, samt gränser på felet i samband med uppskattningar av V. Dessa gränser gör det möjligt för en konstruktör att bestämma den nödvändiga bitbredden av signaler som representerar dessa siffror och fel, och att bestämma när uppskattningar av V kan bildas effektivt och avrundas av, låt oss säga, on-the-fly tekniker. De viktigaste resultaten presenteras här är Proxy Theorem 5.1 och dess Corollary 5.3 med illustrationer av deras tillämpning på division och kvadratrotsalgoritmer. Dessa resultat har kontrollerats/formaliserats med hjälp av HOL Light [1]-teoremet; ett kort utdrag från formaliseringen presenteras i avsnitt 10. Analysen av lågradix DSM för delning och kvadratrot är välförståelig [2]. Analyser av specifika högradix DSM för dessa operationer beskrivs i [3], [4], [5]. Ett ytterligare bidrag av detta papper är tillämpningen av vår generiska DSM analys till en parameteriserad familj av high-radix DSM algoritmer för division och kvadratrot. W. Ferguson är pensionerad från Intel Corporation, Hillsboro, OR 97124.
Under 2018 presenterade Intel Corporation ett forskningsdokument om bevis på riktighet av kvadratrot med hjälp av en siffra seriell metod (DSM) och en teorem bevis (HOL-Light) REF.
Digit Serial Methods with Applications to Division and Square Root
{'venue': 'IEEE Transactions on Computers', 'journal': 'IEEE Transactions on Computers', 'mag_field_of_study': ['Computer Science', 'Mathematics']}