The tag has no usage guidance.

learn more… | top users | synonyms (1)

-1
votes
1answer
43 views

Newbie: hexadecimal editors to make sense of binary files

As a disclaimer, I am a geophysicist, not a computer scientist. I have a binary file with a whole bunch of data in it (it is a large file; 221 MB). I am trying to convert this to something usable but ...
1
vote
1answer
59 views

Long multiplication school method: number of primitive operations to calculate first partial product?

Having got some basics down in regard to addition and explaining it in terms of primitive operations (addition and multiplication), I am now again stuck on understanding the more complicated long ...
0
votes
1answer
17 views

Difference between cordic algorithm and table based methods for elementary functions computation

In this book both Table Based methods and Cordic iterations are explained. computationally speaking i suppose the Table based is usually faster, even though it probably requires more resource, while ...
0
votes
0answers
15 views

Implementing 16bit Adder from 4bit CLAs

It's a bit confusing to me how this 16bit CLA adders work. Since it is hard to implement 16 bit CLA logics and circuits directly, we cascade 4bit CLAs in two's multiples to achieve this. So the ...
1
vote
4answers
312 views

Does a shift operation distribute over XOR

In this question, we abuse the mathematical notation to express bitwise operations in the following way: $\ll$ is a binary left shift $\oplus$ is a bitwise XOR $0b1, 0b110, 0b10 \ldots$ are used to ...
0
votes
2answers
46 views

Generally, does the time it takes to compute (n mod m) depend on the size of n?

Example: Suppose I have a number a with 100 decimal digits, b with 200 decimal digits, and m with 10 decimal digits. Would the speed of the computation a mod m vary greatly from b mod m because of ...
0
votes
0answers
36 views

Using SMT Solvers in formula checking

I'm currently working on a static analysis work in which I need to check whether a given formula is met or not. I hope the following example clarifies my requirement. Suppose we have a list of three-...
4
votes
1answer
74 views

Complexity of division

The article Computational complexity of mathematical operations mentions that the complexity of division in $O(M(n))$, and that "$M(n)$ below stands in for the complexity of the chosen multiplication ...
-1
votes
1answer
36 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
23 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
25 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
46 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
33 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
37 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
104 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
310 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
546 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
67 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
2k 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
143 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
25 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: https://github.com/epibook/epibook.github.io/blob/...
1
vote
1answer
17 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
98 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
30 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$} \\ \mbox{...
2
votes
3answers
263 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
106 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
74 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
53 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
67 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
31 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
62 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
67 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
82 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
53 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
105 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
171 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
56 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
33 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
105 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
210 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
276 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
293 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
26 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
275 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?
1
vote
3answers
178 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
106 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, ...