The tag has no wiki summary.

learn more… | top users | synonyms (1)

0
votes
1answer
20 views

Fast implementation of basic addition algorithm

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
0answers
28 views

One's complement doubt [on hold]

I have checking my notes about binary operations and some doubts have come to me. For example, about one's complement subtraction. The operation is: 8 - 1 using 4 bits. -1 represented in one's ...
0
votes
1answer
34 views

How do you represent basic arithmetic using boolean function?

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
28 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
182 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
48 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
50 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
1answer
240 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
37 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
82 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
34 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
87 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
21 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
88 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
25 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
133 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
63 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
44 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
60 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 ...
7
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
61 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
142 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 ...
9
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
2k 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
167 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
67 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
173 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
602 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 ...
0
votes
0answers
42 views

Is addition polynomial if you add exponential numbers? [closed]

The addition algorithm is polynomial (as far as I know, perhaps I'm wrong). Suppose that $n$ is the number of numbers to be added, and tghe largest one of them is $2^n$. Is this problem still ...
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 ...
6
votes
0answers
92 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
58 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
130 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
70 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
354 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 ...
4
votes
2answers
292 views

Time complexity of base conversion

EDIT As requested, a single question Why can't arbitrary base conversion be done as fast as converting from base $b$ to base $b^k$ ? There is a big time complexity difference, so I am also ...
5
votes
1answer
150 views

How do GPUs compute sines?

I've been wondering lately how GPUs compute sines and cosines, and Google hasn't helped me finding a precise answer. Initially, I was thinking that in order to make the computations as fast as ...
0
votes
1answer
177 views

Number of different output labels in Local Binary Pattern

I'm studying about Local Binary Pattern and I'm having trouble understanding the following part about the number of output labels for binary patterns from Computer Vision using Local Binary Patterns, ...
3
votes
1answer
50 views

What circuit depth is required to add?

If we suppose that we are given two numbers $a$ and $b$ to add, what circuit depth do we require to add them? I'm wondering if $a$ and $b$ are $O(n)$, and thus the amount of bits required to store ...
3
votes
1answer
52 views

Range of CRC-32

What is the range of “the” CRC-32, the one used by Unix, Ethernet, zip, and many other industrial standards? Mathematically, a CRC is defined as follows: let $G$ be the CRC polynomial in ...
3
votes
2answers
130 views

Implement Mathematica's capability of rationalizing machine reals

If I have a variable x bound to a machine precision real in Mathematica, I can use y = FromDigits[RealDigits[x]] then y is ...
1
vote
1answer
73 views

Subtracting binaries using two's complement

I am trying to subtract these two binary numbers: $ 1110 - 1011$ First I convert 1011 to two's complement by doing 1011 to 0100 and then adding 1 to get 0101. Then I add the first number to the ...
2
votes
1answer
97 views

Known bounds on space complexity of multiplication decision problem

Given three numbers $m$, $n$ and $p$ in interleaved binary encoding1, it's obviously possible to check in $O(1)$ space whether $m+n=p$. It's less obvious2 that it isn't possible to check in $O(1)$ ...
2
votes
1answer
66 views

What would be a not arithmetically definable language that is not Turing reducible to another given not arithmetically definable language?

I have this question I'm struggling with. Let $A=\{<i,n>|\;n \in \phi ^{(i)}\}$. In other words, $A$ is the language defined by the set of all pairs $<i,n>$ such that $n$ is $\leq_m$ to ...
2
votes
1answer
59 views

Finding number of numbers dividing n^m exactly p times

Suppose I am given a number $n$ (less than $10^8$) and $m$ (less than $10^7$) and $p$ (less than $10^4$), I have to write a program to find number of numbers that divide $n^m$ exactly $p$ times. ...
2
votes
1answer
334 views

Can I express 100 as a three-digit 9's complement number?

Reading the Appendix A (Binary numbers) of Structured Computer organization by Tanenbaum I've found this exercise: Signed decimal numbers consisting of $n$ digits can be represented in $n + 1$ ...
6
votes
2answers
86 views

Isn't std::bernoulli_distribution inefficient? Designing a bit-parallel Bernoulli generator

C++11 has a convenient Bernoulli RNG, illustrated at http://en.cppreference.com/w/cpp/numeric/random/bernoulli_distribution . However, distilling an entire random integer into a single random bit ...
13
votes
3answers
7k views

Factorial algorithm more efficient than naive multiplication

I know how to code for factorials using both iterative and recursive (e.g. n * factorial(n-1) for e.g.). I read in a textbook (without been given any further ...
1
vote
2answers
55 views

Compute 'permutation' like problem with modulo [closed]

Say, I have some permutation or combination formula like this, $$\frac{n!}{(n-r)!r!},$$ and I want to $\bmod$ the result with some big prime ($10^9+7$ for example). I already tried with modular ...