The tag has no wiki summary.

learn more… | top users | synonyms (1)

0
votes
0answers
34 views

Computing MD5 hashes of huge numbers [on hold]

I need to solve this riddle: So I need to compute $\operatorname{MD5}(2^{1024^2})$. I know what MD5 is and I tried to compute the number inside the parantheses and insert it into an MD5 generator, ...
7
votes
0answers
71 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
187 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
28 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
64 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
35 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
192 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
30 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
103 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
65 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
38 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
55 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 ...
0
votes
0answers
39 views

Why signed magnitude and 1s complement is still being taught?

I was studying some methods for representing binary negative numbers, and one question came to my mind: Why are people still teaching signed magnitude and 1s complement method, if they are not useful ...
1
vote
2answers
102 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
33 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
218 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
67 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
58 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
319 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
52 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
62 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
127 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
259 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
88 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
63 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 ...
11
votes
6answers
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
189 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
73 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
185 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
622 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
112 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 ...
5
votes
2answers
71 views

Quick calculation for $(x^y) \bmod z$

What are the possible ways to calculate $(x^y) \bmod z$ quickly for very large integers? Integers $x,y \lt 10^{10000}$ and $z \lt 10^6$.
6
votes
1answer
490 views

How does binary addition work?

I find binary confusing. I have watched minecraft redstone videos on binary adders, real binary adders, diagrams, etc and yet I have not learned much at all. How does electrons flowing through wires ...