The tag has no wiki summary.

learn more… | top users | synonyms (1)

-1
votes
1answer
25 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 ...
-1
votes
1answer
57 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
19 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, ...
5
votes
4answers
85 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 ...
7
votes
0answers
78 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
22 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 ...
3
votes
3answers
192 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
30 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
65 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
37 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
194 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
31 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
109 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
66 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
42 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
56 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 ...
0
votes
1answer
75 views

Binary digit problem?

Question: If a system has $32k$ bytes and each such byte has unique address(so $32k$ addresses), what is the smallest possible bits that can be use by every byte for the address ? All the bytes ...
1
vote
2answers
120 views

Fast implementation of basic addition algorithm [closed]

Write code for a modified version of the Grade School addition algorithm that adds the integer one to an m-digit integer. Thus, this modified algorithm does not even need a second number being ...
0
votes
1answer
49 views

How do you represent basic arithmetic using boolean function? [closed]

Say you have an arithmetic problem involving two variables, how do you give a Boolean formula for that using standard techniques so that one gets a minimal formula for a given number of quantifiers? ...
-1
votes
1answer
34 views

Bitwise operations on memory addresses

I have to solve a question saying The value of ab if ab & 0x3f equals 0x27. Consider a, b as hex digits. Then b&f means ...
3
votes
2answers
222 views

How can I compute an exponential modulo a large integer?

Does anyone have the computational power to check whether or not $F(m)^d \equiv m \pmod n$, where the values of the variables are found below. According to Wolfram Alpha, I found the result of the ...
1
vote
3answers
71 views

What is different between “Arithmetic Calculation” and “Calculation” in computer science?

What is different when you say "Arithmetic Calculation" and "Calculation" in the context of the computer science? The "arithmetic" in the former seems needless to me since all calculations are ...
2
votes
1answer
60 views

Why is $O(\log_{M/B} N/M)$ the same as $O(\log_{M/B} N/B)$?

Where $N$ is the size of the input, $M$ is the size of your main memory and $B$ the amount of elements that you can transfer in one I/O. My idea is that since $B$ is usually much smaller than $M$ we ...
3
votes
2answers
328 views

Binary Indexed Trees: Why does i & -i work?

I already read this related question on the intuition behind binary indexed trees, and while the answer explains how the tree structure works, it does not really explain how this correlates back to ...
1
vote
1answer
54 views

Twos complement arithmetic

If I have the expression: 1011 0000 1110 -1000 1110 0001 ---------------- Then, I find the twos complement of the second number: ...
-1
votes
1answer
121 views

Encoding of integer arithmetic counting using Lambda calculus [duplicate]

Does anyone know a way of showing an encoding of integer arithmetic counting using Lambda Calculus? Any references related to this would be much appreciated.
2
votes
0answers
72 views

Quick method for approximate integer square roots

I'm looking for an algorithm that -- given a positive integer $n$ -- outputs a positive integer $\bar{n}$ with the following two properties: $(\bar{n}+1)^2>n$; $(\bar{n}-1)^2<n$; So we have ...
1
vote
0answers
93 views

Are rational functions with positive integer coefficients honest?

For every rational function $p(x)/q(x)$ where $p$ and $q$ are polynomials with non-negative integer coefficients, does there exist a polynomial function $h$, such that, if you input a reduced fraction ...
0
votes
1answer
23 views

Computing composite functions

This may not be strictly a computer science question but is related. Whenever there is some function that computes more than two elements, is it possible that all elements are computed at once? Or is ...
0
votes
2answers
137 views

What does it mean to prove that a set of binary integers is regular?

I'm not exactly sure what this question is asking me to do: Show that the set of binary integers (given as strings over $\{0, 1\}$) that are divisible by $3$ is regular, by giving a DFA that ...
1
vote
1answer
29 views

Two's complement overflow

I know that in the case of a 16 bit word, if we have x - 115 in decimal, the smallest x that would cause overflow would be (32767 + 115 + 1)= 32883 because it would represent a number that is larger ...
5
votes
2answers
274 views

Compute square root using (bit) additions and shifts as primitives

Question: Given an $n$-bit natural number $N$, how to compute $\lceil \sqrt{N} \rceil$ using only $O(n)$ (bit) additions and shifts? The tip is to use binary search. However, I could not achieve ...
2
votes
2answers
91 views

How are Signed integers different from unsigned integers once compiled

How are Signed integers different from unsigned integers once compiled? I already know about twos compliment and the like but my question is how can you tell the difference when looking at 8 bit ...
1
vote
1answer
33 views

Separability of the nearest power of two function

I have a function $f$ given by $f(x)=nearest\ upper\ power\ of\ two\ of\ x$ For example, $f(5)=8$ and $f(2)=2$. Are $f(x \wedge y)$ and $f(x+y\mod{N})$ separable over some operator. For example, ...
2
votes
1answer
51 views

Can the Euclidean distance function be computed using only XOR's

The Eulidean distance function $d$ of $x$ and $y$ is given by: $ d(x,y)=\sqrt{x^2-y^2} $ Let us assume that $x$ and $y$ are fixed-point numbers, or $x,y$ are element of some subfield $f_n$ of $F_p$. ...
2
votes
5answers
71 views

What are the minimum memory requirments a microprocessors must have to perform any calculation?

Please excuse my ignorance in low level things. A lot of the written below might be very wrong. As far as I understand (and I might be very wrong), there are two types of memory locations a ...
8
votes
9answers
2k views

Represent a real number without loss of precision

Current floating point (ANSI C float, double) allow to represent an approximation of a real number. Is there any way to represent real numbers without errors? Here's an idea I had, which is anything ...
-2
votes
2answers
64 views

Sum of all binary numbers matching a pattern [closed]

Given $a_1, a_2, a_3, \dots,a_7$ where $a_i \in \{0,1\}$. How to calculate sum of all binary number of the form $$\over {1a_1a_2*a_3**a_4***a_5a_6a_7}$$ where $*$ represent the position of running ...
9
votes
1answer
146 views

Computing the number of bits of a large power of integer

Given two integers $x$ and $n$ in binary representation, what is the complexity of computing the bit-size of $x^n$? One way to do so is to compute $1+\lfloor \log_2(x^n)\rfloor=1+\lfloor ...
10
votes
5answers
2k views

Is 2**x faster to compute than exp(x)?

Forgive the naïveté that will be obvious in the way I ask this question as well as the fact that I'm asking it. Mathematicians typically use $\exp$ as it's the simplest/nicest base in ...
13
votes
7answers
8k views

Why Do Computers Use the Binary Number System (0,1)?

Why Do Computers Use the Binary Number System (0,1)? Why don't they use Ternary Number System (0,1,2) or any other number system instead?
3
votes
2answers
190 views

Japanese Multiplication simulation - is a program actually capable of improving calculation speed? Or am I doomed from the start?

On SuperUser, I asked a (possibly silly) question about processors using mathematical shortcuts and would like to have a look at the possibility at the software application of that concept. I'd like ...
0
votes
3answers
74 views

Is it possible to accurately determine the number of instructions required to multiply or add two integers in a modern processor?

I'm not nearly at the experience level in computer science to be able to properly determine the number of instructions involved in basic ALU calculations, and I'm interested in a certain software ...
5
votes
2answers
187 views

Are there algorithms or circuits that can implement addition without the need for carry flags

Let two numbers $x,y$ be represented in some digit form (binary, octal, ...): $(x_1 x_2 x_3 \ldots)$ and $(y_1 y_2 y_3 \ldots)$. Can we add those numbers such that we do not need to carry over: $x_i ...
2
votes
2answers
624 views

Why addition algorithm is not pseudo- polynomial?

There is something I don't understand. In the Subset Sum problem, in the Dynamic Programming solution, because of binary representation of the sum T, we say it is pseudo-polynomial in run time; we ...
4
votes
5answers
2k views

Optimal Algorithm for checking if a number is a multiple of three

I'm just starting a course on Computational Number Theory and have very little Computer Science background but definitely know enough about the big-O notation. I currently have an assignment to work ...
7
votes
0answers
117 views

Why does floating point modulus exactness matters?

Most Smalltalk dialects currently implement a naive inexact floating modulus (fmod/remainder). I just changed this to improve Squeak/Pharo and eventually other Smalltalk adherence to standards (IEEE ...
0
votes
1answer
63 views

Best (Fastest) Arithmetic Algorithms [closed]

What are the best arithmetic algorithms out there (addition, subtraction, multiplication, division, power, root)? I am looking for algorithms that could be easily extended to multiprecision and ...
7
votes
1answer
135 views

Proving a language (ir)regular (standard methods have failed)

I'm currently trying to prove a language regular (for personal amusement). The language is: The language containing all numbers in ternary that have even bit-parity when encoded in binary. Now, I've ...