The tag has no wiki summary.

learn more… | top users | synonyms (1)

0
votes
0answers
8 views

Tools for examining and comparing files in binary format. [closed]

What are some software tools used for examining files in a binary format. I am looking to analyze CAD files to determine physical properties from patterns found from examining the files in binary ...
1
vote
0answers
79 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
18 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
80 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
24 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
94 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 ...
1
vote
2answers
52 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
42 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 ...
7
votes
1answer
102 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
5answers
807 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
158 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
64 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
167 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
596 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
89 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
51 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
122 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
69 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
328 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
250 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
141 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
129 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
45 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
50 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
127 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
70 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
94 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
65 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
302 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
6k 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
49 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
334 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
121 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
135 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
520 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
6k 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
48 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 ...