The tag has no wiki summary.

learn more… | top users | synonyms

4
votes
2answers
65 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
32 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 ...
5
votes
1answer
110 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 ...
3
votes
1answer
42 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
105 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 ...
2
votes
1answer
60 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
54 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. ...
9
votes
3answers
2k 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
39 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
67 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
251 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 ...
1
vote
1answer
100 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
75 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
122 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
411 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
72 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
4k 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 ...
8
votes
3answers
342 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
270 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 ...
3
votes
1answer
155 views

How can repeated addition/multiplication be done in polynomial time?

I can see how adding 2 unsigned four-bit values is $O(n)$. We just go from the rightmost digits to the leftmost digits and add the digits up sequentially. We can also perform multiplication in ...
7
votes
0answers
419 views

Chained operations on sequences with two operators

Given a binary expresion tree, with addition and multiplication operations, how can we optimize it's evaluation? Can we learn from matrix chain multiplication? A generalization of matrix chain ...