7

Observe that $ab=\frac{1}{2}\left((a+b)^2-a^2-b^2\right)$, hence multiplication requires three squaring operations and 3 additions/subtractions (division by 2 is easy), which means squaring is asymptotically as hard as multiplying.


4

When the time complexity of a computation such as adding two $\lg n$-bit numbers $x$ and $y$ is considered, it is often assumed that the bits in $x$ and $y$ are available all at once unless the algorithm in question is bit-serial and bits of $x$ and $y$ arrive over time. So, while it is true that every bit counts and we can't ignore any given bit, one doesn'...


2

Copy the second number (from the second tape) to the first tape, and then use the already existing TM that subtracts the numbers


2

I have a solution that I just found looking at the patterns, and I checked the pattern up to decimal 31 or binary 11111 or Gray 10000, and it worked quite fine, and I am confident enough the answer will carry through larger values too. Take a Gray code, and count the number of 1's: Case I: Odd number of 1's: flip the bit one position before the last '1'. ...


1

I haven't edited my question, but in case others are here: this thesis addresses the question I was intending (https://core.ac.uk/download/pdf/52104064.pdf), finding e.g. 1189 average transitions required for a certain architecture for a 16-bit by 16-bit multiply that's completely random bits. \


1

$100 011 110 101$ if is taken as SM in 12bit is $-245$ decimal and $011 100 001 010$ is $1802$ decimal, so we obtain $-245-1802=-2047$. $2047$ in binary is $11111111111$ with $11$ bits so for minus we add one more $1$ to left = $111111111111$. It is octal 7777.


1

Background Writing a number in base $r$ means to write it in the form $$a_0+a_1r+a_2r^2+\ldots+a_nr^n$$ where $0\leq a_i< r$, for all $i=0,1,\ldots,n$. The positional notation that we use consists in just writing the digits $a_i$ from right to left $$(a_na_{n-1}\ldots a_2a_1a_0)_r$$ Some people write parentheses and maybe the radix as a subscript. Some ...


1

You are confusing two or three different concepts here: Languages: these are collections of strings. Context-free grammars: this is a specific way to describe languages. Parsing: this is the process in which a computer "understands" input. You haven't explained what you mean by "arithmetic"; some people think of arithmetic as the set of ...


1

This depends on the rules of your programming language, which you need to check. For any fixed size integral type that has more than the single value zero, there are integers that can be represented in the type, for which the mathematical value 2*x cannot be represented. So something has to give. In C and C++, a signed integer overflow is undefined behaviour,...


1

Your answer is nearly right. So x is an unsigned negative value of k bits. The smalles possible value of x is representet by the 2's Complement number 1000....0. If you multiply this number by 2 (or logical shifting it by 1, which is equivalent) you end up with the number 0000...0 which is 0. And therefore (x*2)<0 is false.


1

One common way to work with binomial coefficients without overflow is to use prime factorisation. Legendre discovered the formula for this, and it is worth proving it for yourself. The factorial of a number can be factorised as powers of primes: $$n! = p_1^{q_1} p_2^{q_2} \cdots$$ where: $$q_i = \sum_{k=1}^{\left\lfloor \log_{p_i} n \right\rfloor} \left\...


1

Let $x=0.11001100...$. in base $2$. Then $16x=1100.\overline{1100}\implies 15x=12\implies x=4/5$.


1

Classical formula for proper fraction is $$(0.a_{-1}a_{-2}a_{-3}\cdots)_2 = \left(\sum\limits_{k=1}^{\infty}\frac{a_{-k}}{2^k}\right)_{10}$$ Where for $a_{-k}$ we have $k \in \mathbb{N}$ and $a_{-k}\in \{ 0,1\}$. As you see for indexing is taken negative numbers. In your example $$(0.11001100...)_2 =\left( \frac{1}{2^1}+\frac{1}{2^2}+\frac{1}{2^5}+\frac{1}{...


1

Here is how to convert the fractional part from hexadecimal to binary: $$ (0.25)_{16} = \frac{2}{16} + \frac{5}{16^2} = \frac{0 \cdot 8 + 0 \cdot 4 + 1 \cdot 2 + 0 \cdot 1}{16} + \frac{0 \cdot 8 + 1 \cdot 4 + 0 \cdot 2 + 1 \cdot 1}{16^2} = \\ \frac{0}{2} + \frac{0}{4} + \frac{1}{8} + \frac{0}{16} + \frac{0}{32} + \frac{1}{64} + \frac{0}{128} + \frac{1}{256} =...


1

When you use normal multiplication, multiplicand and multiplier are represented using (Sign + Magnitude) representation. So effectively 1101 is +(13) in Decimal and (1110) is +14 in decimal as they represent the magnitude. Sign bit would be separate. So the result is (+13)*(+14) = +182 which is 1011 0110 in binary. When you use booth multiplication, operand ...


1

You need to subtract 01010011 from 10100110. 10100110 - (01010011) So find the 2's complement of 01010011 which is 10101101 and just add it to 10100110 01011000 <=carry bits 10100110 +10101101 ---------- 101010011 <= Result, but the extra 9th bit to the left of MSB is stored outside a register in a special carry out flip-flop Now the ...


1

You cannot represent –173 using 8 bits, since the range is –128 to 127. To subtract two numbers in two's complement, you use the identity $a - b = a + (-b)$. In your case, $a = 10100110$, $b = 01010011$, and $-b = 10101101$. Adding $a$ and $-b$, there is overflow, so you know that the number is outside the range.


1

For any such $X$ we have $X\le_mTh(\mathbb{N})$ but not conversely (and in fact $Th(\mathbb{N})$ is vastly more complicated than $X$). To see that $X\le_mTh(\mathbb{N})$, we want to translate a question of the form "Is $n\in X$?" into one of the form "Is $\psi_n$ a true sentence?" for some appropriate sentence $\psi_n$. Now "$n\in X$&...


1

When we multiply, the answer is stored in 2 registers. When we multiply 2 numbers the results length does not exceed ($n_1+n_2$) where $n_1$ is length of 1st number and $n_2$ is length of second number. So there is no chance of overflow here as the length of 2 registers is greater than or equal to $n_1+n_2$.


1

Theorem B on page no. 272 of the book states that, if $v_{n-1}$ $\geqslant$ $\lfloor b/2 \rfloor$, then q ∈ [ q̂ - 2 , q̂ ]. Therefore, the algorithm is valid only when $v_{n-1}$ $\geqslant$ $\lfloor b/2 \rfloor$, which makes $v_{n-1} \neq 0$ obvious. To ensure this we need to multiply both u and v by a factor ${(= (base-1) / v_{n-1})}$.


Only top voted, non community-wiki answers of a minimum length are eligible