Tagged Questions

0
votes
0answers
54 views

Arithmetic Coding Example

I have a question for static arithmetic coding which I have done in class but I can't seem to figure out where I got the answers. It's a bit hard to get in touch with my lecturer at the moment so I'm ...
0
votes
0answers
36 views

How to represent probability as Integer - Arithmetic coding

I am doing an assignment for a class in college where we have to write an arithmetic encoder / decoder in Java. In this video, it shows how to set up / define all the variables required for the ...
2
votes
0answers
41 views

Clarification of variable values in Arithmetic Coding algorithm

I have been trying to follow this video to implement my own Arithmetic Coding algorithm in Java. I am having a bit of trouble figuring out what some of the variables in the video should be. For ...
3
votes
1answer
41 views

Static Arithmetic Encoding/Adaptive Arithmetic Encoding Algorithm

I'm trying to learn how to implement the Arithmetic Encoder algorithm for one of my classes. The thing is the notes we have explaining the actual algorithm are a bit on the confusing side. I have ...
1
vote
1answer
83 views

How to solve/transform/simplify an equation by a simple algorithm?

MathePower provides an form. There you can input a formula (1st input field) and a variable to release (2nd input field) and it will output a simplified version of that formula. I want to write a ...
0
votes
1answer
84 views

Is the result always n+1?

I'm reading a book on algorithms by Kurt Mehlhorn and Peter Sanders. On page 2, the following Theorem is stated: The addition of two n-digit integers requires exactly n primitive operations. The ...
3
votes
1answer
192 views

Karatsuba Multiplication

Karatsuba's equation to reduce the amount of time it takes in brute force multiplication is as follows (I believe this is a divide-and-conquer algorithm): $$ x y = 10^n(ac) + 10^{n/2}(ad + bc) + bd ...
1
vote
0answers
78 views

Does the shifting square root method work for non-integer bases?

Under "methods of computing square roots", Wikipedia states that the digit-by-digit calculation method, of which the shifting $n^{th}$ root algorithm is a generalization, works for all bases, but the ...
4
votes
2answers
202 views

Time complexity to calculate a digit in a decimal

As we know, it is quiet fast to calculate any digit in a rational number. For example, if I'm given 1/7 (0.142857 142857 ...) and any integer K, I could easily return the Kth digit of 1/7, by doing a ...
0
votes
0answers
126 views

Division of two numbers issue

I'm not much of a maths genius here, so I was hoping you could help me out. I'm currently developing an algorithm for a javascript calculator that has two variables- both with a minimum and a maximum ...
4
votes
1answer
238 views

How to add or multiply decimal numbers?

The tag ''calculus'' may not fit for this question but I couldn't think of anything else. Please feel free to change it. Suppose $a=0,a_{-1}a_{-2}a_{-3}\ldots$ and $b=0,b_{-1}b_{-2}b_{-3}\ldots$ are ...
2
votes
2answers
200 views

Rewriting repeated integer division with multiplication

In many programming languages, such as C and C++, integer division of positive numbers is defined by simply ignoring the remainder. $5 / 2 == 2$. In general, is it true of positive integers $a$, $b$, ...
5
votes
2answers
181 views

How can I write an algorithm to perform the following calculation exactly? (references accepted)

Given natural numbers $N, K, m, C$, with $3^{m/3}K>C$, I want to be able to write an algorithm to exactly compute the number $$ \left\lceil \log_3 \left(\frac{N}{3^{m/3}K-C}\right) \right\rceil $$ ...
0
votes
2answers
234 views

Floor and ceiling on fractions

Is there an algorithm to compute ceil and floor on fractions without computing the division between the numerator and denominator (to avoid losing precision on big numbers)? A trivial example: ...
1
vote
1answer
193 views

Integer multiplication without intermediary values

I'm making a programming project for learning purposes, in which I try to calculate powers of very large numbers in as short of a time as possible. One thing I could do is to try to do multiplication ...
5
votes
2answers
225 views

Is there a log-space algorithm for divisibility?

Is there an algorithm to test divisibility in space $O(\log n)$, or even in space $O(\log(n)^k)$ for some $k$? Given a pair of integers $(a, b)$, the algorithm should return TRUE if $b$ is divisible ...
2
votes
2answers
556 views

Schönhage-Strassen multiplication

I am trying to implement the Schönhage-Strassen algorithm (SSA) for multiplying large integers, but it only gives the right result if all $\delta_j$ are zero. I'll explain what I mean by this: SSA ...
1
vote
0answers
655 views

Teach me a simple, efficient division algorithm

I want to implement arbitrary-precision arithmetic in JavaScript for non-negative integer numbers. Long division isn't efficient if instead of the usual 10 digits (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) there ...
1
vote
1answer
122 views

Number of operations in grade school algorithm for multiplying 577 and 423

Given 577 x 423 with grade school algorithm you calculate 577 x 3 = 1731 577 x 2 = 1154 577 x 4 = 2308 These are 3 multiplications of a number by a single digit. Then, you go on and add 1731 + ...
2
votes
1answer
472 views

Calculate the root of a number without useing the root function or decimal numbers

I'm trying to build a program in c# which will calculate prime numbers for me. I'm using the BigInteger class to work with 'endless' numbers. However, there is a big down side on this function, I ...
5
votes
2answers
3k views

How to calculate the number of decimal digits for a binary number?

I was going to ask this on Stack Overflow, but finally decided this was more math than programming. I may still turn out to be wrong about that, but... Given a number represented in binary, it's ...