The tag has no usage guidance.

learn more… | top users | synonyms (1)

-1
votes
1answer
33 views

How fast can one compute the power of a number?

Let $x \in \mathbb{R}$ and $k \in \mathbb{Z}^+ \cup \{0\}$ then how fast can one compute $x^k$? If $x, k \in \mathbb{Z}$ then I guess this previous discussion already settled that, How many ...
1
vote
0answers
19 views

Dual Signed Kahan Summation

NOTE: This is for a project I'm working on for fun, NOT production code. So I'm working on a pet project that involves reading data in from a sensor and summing it up. The values are mostly ...
1
vote
1answer
19 views

half precision floating point multiplication

A = 0 10011 0011110111 B = 1 00011 0010011000 exponent is 15, mantissa is 10 bits and first bit is implicit. Can somebody please tell me the final answer cause I am having trouble figuring ...
1
vote
1answer
37 views

Why do floating point additions sometimes produce equal results? [duplicate]

I have tried two sentences on my computer : 2 + 10^(-18) == 2 2^(-55) + 2^(-57) == 2^(-55) My computer gives TRUE and FALSE respectively. Why does the computer ...
-5
votes
1answer
42 views

Addition recursively [closed]

How would you recursively add numbers? Just in terms of pseudocode how would one approach such a problem in the most efficient run time
0
votes
2answers
30 views

Is the number of operators always one less than the number of values in an arithmetic Reverse Polish Notation expression with only binary operators?

Is the number of operators always one less than the number of values in an arithmetic Reverse Polish Notation expression with only binary operators? This question seems very trivial, but I don't know ...
3
votes
1answer
35 views

Help me understand the logic behind x - y in binary by boolean?

x and y are 4 bit signed numbers (2s complement..) x - y can be obtained by: !(!x + y) I know that in 2s complement ...
4
votes
4answers
90 views

XOR two numbers

Is there an intuitive meaning of XOR of two numbers not involving binary and just decimal? Or is is always converted into binary and then XORed?
8
votes
1answer
294 views

Minimal basis for set of binary vectors using XOR

I would be surprised if this isn't a well-studied problem, but I'm not sure what else to search for at this point: you're given a set of binary $n$-vectors $S \subset \{0,1\}^n$. The problem is to ...
0
votes
1answer
42 views

Is it possible to compute -12 (decimal) in 4 bits binary

This is what I have so far 1 1 0 0 Switch values by 2s Complement 0 0 1 1 + 1 0 1 0 0
3
votes
1answer
533 views

Complexity of multiplication

I've been reading around the area of complexity and arithmetic operations using logic gates; one thing that is confusing me is that \begin{equation} \Theta (n^{2}) \end{equation} is quoted as being ...
3
votes
1answer
61 views

What is the XNOR of 3 or more inputs?

We know that for 3 variables (A=0,B=1,C=1), f$_1$ = (A XNOR B XNOR C) = 1, since the input has even number of 1's. But if we were to do this step by step, f$_2$ = (A XNOR (B XNOR C)) = (A XNOR (1 ...
-1
votes
1answer
33 views

This opertion gives overflow and carry?

Take this example in 2's complement representation with 8 bits. 1111 1110 + 1111 1110 ( -2 + -2 = -4 ) Calculation: ...
2
votes
1answer
1k views

Full Adder vs. Half Adder

I'm having some trouble figuring out where the "Carry in" value comes from in respects to a one bit full adder diagram. I understand the below half adder, but my question is: is the the output of ...
6
votes
1answer
139 views

Sum of all products of subarrays

For any three-dimensional array $A$ of size $n_1 \times n_2 \times n_3$ let $P(A)$ be the product of all its elements, i.e. $$P(A) = \prod_{i_1 = 1}^{n_1} \prod_{i_2 = 1}^{n_2} \prod_{i_3 = 1}^{n_3} ...
0
votes
1answer
22 views

EPI question on multiplying two integers

The Elements of Programming Interviews book has a question on "computing x*y without arithmetical operators" (question 5.5). The solution is here: ...
1
vote
1answer
14 views

How to Apply Binary Transformations?

One of the steps in Binary Index Tree algorithm is to find a node's parent which is done by un-setting the rightmost SET bit. For example: if a node has index 1010 than it's parent is 1000. To apply ...
-2
votes
1answer
79 views

Turing machine for adding numbers

I'm having trouble in a certain problem. I have to write a TM that gets as an input strings $\#x\#y$ such that $x,y \in \{0,1\}^*$, and writes to the tape the output $z\#x\#y$ where $z = x+y$, all ...
1
vote
0answers
27 views

Understanding exponential computation by digit recurrence

I've met in a book the following algorithm that computes the exponential: Input: $t, n$ ($n$ is the number of steps) Output: $E_n$ $\begin{array}{l} \mbox{define $t_0 = 0$ ; $E_0 = 1$} \\ ...
2
votes
3answers
245 views

Counting an integer's divisors without just enumerating them (or estimating if not possible)?

I'm trying to count the number of divisors an integer $n$ has. The simple way to do this is to just enumerate all integers from 1 to $\sqrt{n}$, and count how many integers evenly divide $n$. For ...
2
votes
1answer
88 views

How to XOR two binary numbers having different lengths?

If we have: x = 1101 and y = 101 How to XORing these numbers?
1
vote
1answer
71 views

What this subnetting restriction means

I was reading Data Communication book by Forouzan in which there is a one restriction put on CIDR subnetting by Internet authorities: First IP address in the block should be evenly divisible by ...
1
vote
1answer
47 views

How to revert a carryless polynomial multiplication?

In the carryless multiplication of two polynomials in a 8bit environment. Is it possible to obtain the original 8bit values from the result? As an example: (x11 + x10 + x9 ) + (x7 + x5 + x4 + x3 + ...
2
votes
0answers
56 views

How to design a simpler Version of CARDIAC (Cardboard Illustrative Aid to Computers)?

I'm trying to make a simpler version of CARDIAC for only performing addition. Now, I am encountering several problems in making something similar and looking for some ideas (I'm new to Computer ...
2
votes
0answers
28 views

How can I determine if an algoritm can be expressed as a boolean circuit?

Suppose I want to express Data Encryption Standard(DES) encryption algorithm as a boolean circuit. How can I determine if what I want is practical, and if it is how can I do it?
1
vote
1answer
59 views

Adder circuit with sign bit (not twos complement)

I've found and implemented a full adder to be able to do unsigned or two's complement addition on wikipedia: https://en.wikipedia.org/wiki/Adder_(electronics)#Full_adder However, in my particular ...
2
votes
1answer
62 views

How many basic operations are there in an algorithm for the simple multiplication of two numbers of equal length?

BACKGROUND: Note: The following question arose in my mind when watching this lecture (watch at 5:30 minutes if you will). Assumption: Just for the sake of this question, let's assume that the term ...
2
votes
1answer
67 views

Alternative Method for Computing Two's Complement Binary -> Decimal

I proposed this method of converting a two's complement binary number to decimal to my professor and he said it was wrong. Some older guy in the class just shook his head at me and gave me a ...
1
vote
0answers
49 views

Dividing/Multiplying Numbers Stored in two memory locations

I have two numbers x and y. The upper bits of x are stored at location m, while the lower bits of x are stored at location n. The upper bits of y are stored at location i, while the lower bits of y ...
2
votes
1answer
87 views

In fast multiplier circuits, what is the difference between a Counter and a Compressor?

When working on fast parallel multiplier circuit designs, like Wallace tree multipliers or Dada tree multipliers I found many papers and books refer to different components used in the tree to reduce ...
5
votes
3answers
167 views

Data types for storing arbitrarily much information

I've heard that YouTube had a problem with the view count on Gangnam style since the number of views exceeded the variable byte size. What's the problem with creating really large variables? Why ...
0
votes
0answers
52 views

Could you explain this signed fixed point number equation?

How do I interpret this equation? Decimal value of signed fixed point number $-2^3+2^0+2^{-1}+2^{-2}$ $$ V = (-1)^{b_{N-1}}\times 2^{N-P-1} + \sum_{i=0}^{N-2}(b_i\times 2^i)\times 2^{-P}\,.$$ ...
-1
votes
1answer
31 views

Find variance within one pass

Given a list of real numbers. Is it possible to find the variance with no more than 1 iteration with constant space complexity? My intuition is that it is not possible. But how do I prove it ...
2
votes
2answers
100 views

Why is there more frequent overflow in normalised Floating Point

I read that overflow is more frequent when we work with normalised mantissas. Why is this? Is it because when we adopt a normalised representation, our range is smaller than in a unnormalised ...
-1
votes
1answer
204 views

Computing the number of squares which are intersected by a line internally

There's a line from (x1,y1) to (x2,y2) in a grid of squares of unit length. Write a program to compute the number of squares which are intersected by the line internally, i.e squares which are only ...
3
votes
0answers
28 views

Running time for threshold function evaluation?

A threshold function is a function $f: \{0,1\}^n \to \{0,1\}$, defined by $n$ integer-valued weights $w_1, w_2, \ldots, w_n$ and an integer valued threshold value $w_0$. It works as follows: $$f(x_1, ...
6
votes
4answers
230 views

Calculating the number of multiplications necessary to evaluate a polynomial

I was watching a lecture and got confused over a slide. This is what it says: Consider a polynomial - first representation $$P = 2 + 4x^{3} + 8x^{6} + 7x^{25} + 6x^{99}$$ The ...
9
votes
1answer
242 views

Algorithm for multiplying multivariate polynomials

Let $R$ be a commutative ring. Let $f(x_1, \dots, x_n), g(x_1, \dots, x_n)$ be two multidimensional polynomials in $R$ with maximal total degree $\delta$. How fast can we compute the product of $f$ ...
1
vote
0answers
25 views

pragmatic way to compute/ search/ match MSBs operation

consider integers represented as base 2 (strings). define a relation called "n-msb matching" that is true when the 1st n msbs (MSB is "most significant bits") match (of two integers). what is a ...
4
votes
4answers
268 views

How was the ALU implemented in the first computer (i.e., Babbage's analytical engine)?

I've seen circuit level implementations of ALU's before, but how are NOT/AND/ADD performed mechanically?
0
votes
3answers
103 views

confused about XORing and addition modulo 2

it's my understanding that when you XOR something, the result is the sum of the two numbers mod 2. why then does 4^2 = 6 and not 0? 4+2=6, 6%2 doesn't equal 6. I must be missing something about what ...
2
votes
1answer
101 views

What is this trapezoid-shaped logic component?

This is from http://www.cis.upenn.edu/~milom/cse240-Fall05/handouts/Ch05.pdf , slide 9. From this diagram, I recognize 0001 as the opcode, which corresponds to the ADD instruction. I recognize 011, ...
2
votes
1answer
65 views

Does last carry bit get added onto the sum calculated by full adder?

Note: This problem is from Introduction to Computing Systems: From Bits and Beyond(2nd) edition, 3.15, page 86. The Problem: I was able to do the problem and ended up with sum being 0010 and the ...
1
vote
1answer
238 views

Why doesn't the binary fraction representation match the decimal fraction representation?

The Problem: What value does the hexadecimal number x55544552 represent in data type IEEE floating point? My Work:     I first wrote out that hexadecimal number in binary and got ...
0
votes
1answer
95 views

How many zeros should be in front of two's complement model?

The Problem Convert 256 to its 2's complement representation. My Work    I know that 256's representation in unsigned binary is 100000000. What I know from working with two's complement ...
4
votes
2answers
182 views

Standard constructive definitions of integers, rationals, and reals?

Natural numbers are defined inductively as (using Coq syntax as an example) Inductive nat: Set := | O: nat | S: nat -> nat. Is there a standard way to define ...
1
vote
2answers
71 views

Cost of shifting a number

I was wondering what would be a time complexity of shifting a binary or a decimal number? For example: 0011, when I shift it left I get 0001. I was thinking that the time complexity is $\Theta(n)$, ...
0
votes
1answer
60 views

The logic behind one's complement addition

For my computer science class I need to finish a project where I desperately need to understand logic of one's complement and two's complement. I already know how to construct these and also how ...
0
votes
1answer
74 views

SAT for arithmetic

Given two integers $X$ and $Y$, each can be encoded in binary $X=(x_4 x_3 x_2 x_1)$ and $Y=(y_4 y_3 y_2 y_1)$, how do I encode the constraint $$|X-Y|\geq n \quad\text{and}\quad|X-Y|= n$$ when $n$ is ...
2
votes
1answer
30 views

What is considered arithmetic when dealing with bits?

In a recent homework question we were asked to implement a program that would use only bitwise operations. From our notes, this includes & | ^ ~ >> << and >>>. We are not allowed to use ...