Scribd Logo
Upload

Welcome to Scribd!

  • 44 views

    Base Conversion: Dr. Arunachalam V Associate Professor, SENSE

    Uploaded by

    Anil Kumar Gorantala
    Base conversion is necessary to translate between the binary numbers used internally by computers and the decimal numbers preferred by humans for input and output, with naive conversion algorithms becoming inefficient for huge numbers, but more optimized divide-and-conquer strategies allow conversions to be performed more quickly in subquadratic time.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Base Conversion: Dr. Arunachalam V Associate Professor, SENSE

    Uploaded by

    Anil Kumar Gorantala
    44 views8 pages
    Base conversion is necessary to translate between the binary numbers used internally by computers and the decimal numbers preferred by humans for input and output, with naive conversion algorithms becoming inefficient for huge numbers, but more optimized divide-and-conquer strategies allow conversions to be performed more quickly in subquadratic time.

    Original Title

    10_Base_Conversion.pdf

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Base conversion is necessary to translate between the binary numbers used internally by computers and the decimal numbers preferred by humans for input and output, with naive conversion algorithms becoming inefficient for huge numbers, but more optimized divide-and-conquer strategies allow conversions to be performed more quickly in subquadratic time.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    44 views8 pages

    Base Conversion: Dr. Arunachalam V Associate Professor, SENSE

    Uploaded by

    Anil Kumar Gorantala
    Base conversion is necessary to translate between the binary numbers used internally by computers and the decimal numbers preferred by humans for input and output, with naive conversion algorithms becoming inefficient for huge numbers, but more optimized divide-and-conquer strategies allow conversions to be performed more quickly in subquadratic time.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 8

    Base Conversion

    Dr. Arunachalam V
    Associate Professor, SENSE
    Base conversion
    • Since computers usually work with binary numbers, and human prefer decimal
    representations, input/output base conversions are needed.
    • In a typical computation, there are only a few conversions, compared to the
    total number of operations, so optimizing conversions is less important than
    optimizing other aspects of the computation.
    • However, when working with huge numbers, naive conversion algorithms may
    slow down the whole computation.
    • All the numbers are represented internally in base - usually a power of 2 -
    and externally in base B - say a power of 10.
    • When both bases are commensurable, i.e., both are powers of a common
    integer, like β = 8 and B = 16, conversions of n-digit numbers can be
    performed in O(n) operations.
    • We assume here that and B are not commensurable.
    • One might think that only one algorithm is needed, since input and output are
    symmetric by exchanging bases and B.
    • Unfortunately, this is not true, since computations are done only in base .
    Quadratic Algorithms

    Verify the algorithms using S = 189 ; = 1011 1101


    Subquadratic Algorithms
    • Fast conversions routines are obtained using a “divide and conquer” strategy.
    • Given two strings s and t, we let s || t denote the concatenation of s and t.
    • For integer input, if the given string decomposes as = || where
    has k digits in base B, then , = , + , ,
    • Where Input(S,B) is the value obtained when reading the string S in the
    external base B.
    Verify the algorithms using S = 189 ; = 1011 1101
    Verify the algorithms using S = 189 ; = 1011 1101
    Reference
    1. Chapter 1.7 of Richard P Brent and Paul Zimmerman, “Modern
    Computer Arithmetic”, Cambridge University Press 2010.
    Next Class

    MODULAR ARITHMETIC

    Start reading the Chapter 2 of Richard P Brent and Paul Zimmerman, “Modern
    Computer Arithmetic”, Cambridge University Press 2010.

    You might also like