The tag has no wiki summary.

learn more… | top users | synonyms (1)

2
votes
1answer
40 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
50 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
1k 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
59 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 ...
6
votes
1answer
66 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 ...
7
votes
5answers
252 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
149 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
63 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
165 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
586 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
85 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
49 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
118 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
68 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$.
1
vote
0answers
35 views

Computing n! modulo p [closed]

I found an intersting problem. I have to compute n! modulo p and can't figure out a way of doing this. For small ns I can ...
6
votes
1answer
293 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
221 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
130 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
101 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
42 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
49 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
123 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
69 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
90 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
63 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
58 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
234 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
84 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 ...
12
votes
3answers
4k 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
44 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 ...
2
votes
1answer
68 views

Calculate the number of elements after multiplying/adding two polynomials

Suppose I have two polynomials $f(x)$ and $g(x)$ and I somehow represent their coefficients. I have a couple of ways to hold a polynomial depending on how many significant coefficients the polynomial ...
2
votes
2answers
300 views

How many recursive calls are made by this gcd function?

In the following function, let $n \geq m$. int gcd(n,m) { if (n % m == 0) return m; n = n % m; return gcd(m, n); } How many recursive calls are ...
4
votes
1answer
71 views

Bitarithmetrics to Base X

I've got the following theoretical problem which puzzles me a bit: I can obtain a string of n bytes (as octets, one byte = one octet = eight bits) of random data. I need to preserve the randomness ...
1
vote
1answer
117 views

Multiplying intervals in Two's complement

I want to perform some interval-operations, and for addition, subtraction, and logic-/shift-operators, that works very well. The only problem I have is the multiplication. An interval $[a, b]$ ...
0
votes
1answer
76 views

Finding largest value for $\frac{\phi(i)}{i}$ for $i \in (2, N)$

I need to find largest value for $\frac{\phi(i)}{i}$ for $i \in (2, N)$ where $N$ can be as large as $10^{18}$. I tried this approach , but is too slow. Finding the just smallest prime number to $N$, ...
0
votes
1answer
132 views

Does converting algorithms into elementary recursive form preserve runtime bounds? [closed]

There is the complexity class ELEMENTARY that captures all problems that can be solved by using elementary recursive function only. So if algorithms for solving problems in some complexity class (e.g. ...
-1
votes
2answers
454 views

Network modem question

How would I solve the following can anyone help me.I know MIPS is basically how many instruction the processor can do per second but what should I do? Assume that we are receiving a message across a ...
2
votes
1answer
73 views

Dividing in modulo prime arithmetic

I am looking for a way to implement division in modular arithmetic using modulo prime. The method I found in math books is to try $u$ such that $au \equiv 1 \pmod{p}$ $b/a \equiv bu \pmod{p}$ ...
4
votes
4answers
5k views

The math behind converting from any base to any base without going through base 10?

I've been looking into the math behind converting from any base to any base. This is more about confirming my results than anything. I found what seems to be my answer on mathforum.org but I'm still ...
1
vote
1answer
44 views

Subtracting a two's complement value from another two's complement value

I'm trying to solve the following problem: $$ 6AD3 - AF20 $$ Both of these are hex values in two's complement. I keep getting one answer but it's turning out worng. What I tried to do, was take ...
4
votes
2answers
157 views

Minimizing the full adder - where did this XOR come from?

When minimizing the full adder, I don't understand why $A(\bar{B}\bar{C} + BC)$ reduces to $A\overline{(B\oplus{C})}.$ $(\bar{B}\bar{C} + BC)\to (B\oplus{C})$ is partially decipherable, but why is ...
2
votes
1answer
131 views

Why is binary subtraction referred to as the invert-add-shift-add method?

I'm being asked this question for my computer conceptes class, can't find anything about this in my text book, and have only been able to find half-baked answers googling it. Why is binary ...
1
vote
2answers
365 views

Subtracting an integer from an ASCII number

Theoretically, if I were to subtract the number 10 from the ASCII character 10 (which is really 00110001 00110000), what would I get? Does the computer add both ASCII characters and subtract?
0
votes
2answers
98 views

Which is more computationally efficient: multiplication or 0 padding?

On a PC I am implementing an algorithm in which a number from a look table will be chosen randomly, and will be multiplied by 1000 or 10000. Instead of multiplying by 1000 or 10000 I am thinking of ...
3
votes
1answer
3k views

Normalizing the mantissa in floating point representation

How to represent $0.148 * 2^{14}$ in normalized floating point arithmetic with the format 1 - Sign bit 7 - Exponent in Excess-64 form 8 - Mantissa $(0.148)_{10} ...
8
votes
3answers
478 views

Finding maximum and minimum of consecutive XOR values

Given an integer array (maximum size 50000), I have to find the minimum and maximum $X$ such that $X = a_p \oplus a_{p+1} \oplus \dots \oplus a_q$ for some $p$, $q$ with $p \leq q$. I have tried this ...
1
vote
1answer
293 views

Calculating Binet's formula for Fibonacci numbers with arbitrary precision

Binet's formula for the nth Fibonacci numbers is remarkable because the equation "converts" via a few arithmetic operations an irrational number $\phi$ into an integer sequence. However, using finite ...