0
votes
1answer
56 views

Algorithm for a counter [on hold]

I am looking for an accurate algorithm for calculation required in any kind of counter, Like for example I have two values a: max 48 bits b: max 30 bits x: (a << 30) | (b); Now, if value of b ...
0
votes
1answer
27 views

Is there a quick way to obtain $a,b$ in $ax+by = z$ where $x,y,z$ are fixed and $x+1 = y$?

Suppose that all numbers are postive integers. Let $x,y,z$ be fixed/given and $x+1=y$. Then would there be a quick way to find set of solutions $(a,b)$ that satisfy $ax+by=z$? "Quick" would be ...
0
votes
0answers
14 views

Unrolling and rerolling with a different thickness

I have two rolls, the main one with two layers of material and the secondary one with just one of them. As the main one unrolls it loses one layer of thickness, and simultaneously the second one has ...
0
votes
5answers
75 views

Refresh summation formulas

I am trying to refresh on algorithm analysis. I am looking for a refresher on summation formulas. E.g. I can derive the $$\sum_{i = 0}^{N-1}i$$ to be N(N-1)/2 but I am rusty on the and more complex ...
0
votes
0answers
23 views

Reaching a proof

I'm trying to solve this problem: Link. After reading the problem, I realized that to start off, we can imagine the problem only in the positive axis, working only with $|x|$. Then, we want the ...
4
votes
1answer
43 views

Problem understanding Master theorem

I'm studying the Master theorem (for the analysis of recursive algorithms) and I perfectly understand why a binary search is of order $\log_2(n)$. I also understand that if we formulate it as $T(n) ≤ ...
1
vote
0answers
51 views

Absolute values nested multiple times

Is there any algorithm to quickly determine "zero points" (i.e. points with undefined derivation) of absolute values functions which are nested multiple times? I do know, that any part of this ...
0
votes
3answers
43 views

How do you solve a equation by converting to logarithm form for the problem$3e^{x-4} +2=83$?

$3e^{x-4} +2=83$ I understand converting logarithms but i dont understand how to convert e into log form and solve. help would be deeply appreciated.
0
votes
1answer
35 views

Reversing $\sum_0^kx\cdot2^i$

I'm trying to write an algorithm, and the easiest way I found for explaining the mathematical problem I'm facing is the following: Assume you have $x$ US dollars and you're gambling on a roulette. ...
0
votes
2answers
26 views

Relating number of iterations to n

n = length of list with more than n > 0. index = 0 step = 1 while index < n: index = index + step step = step + 1 return How many times will the loop ...
0
votes
1answer
39 views

How to come up with formula for this number growth

I have difficulties to come up with a formula to achieve this in my programming challenge : The input number ranges between 100 to 10.000 (all integers), then the output would be 0.1 - 10, so the ...
2
votes
1answer
55 views

What's the most efficient algorithm to determine the relative ordering of an unknown set of values?

This comes from a question on Arqade. The background is, there's a mall level. Vlad the organized crime boss wants $50,000 worth of mall property destroyed. Your task is to shoot and blow ...
1
vote
0answers
74 views

Richardson's theorem for constants

It's known that there is no algorithm for deciding for any elementary function is it identically zero or not (http://en.wikipedia.org/wiki/Richardson%27s_theorem ). But if I consider only constants - ...
0
votes
2answers
192 views

What is the point of the median?

It seems like the purpose of the median is to ignore a specific type of data point. More specifically, it is used to make outliers have a lower weight than other data points on an average. Why not ...
1
vote
1answer
58 views

simple maths problem

N locations are numbered from 0 to N-1. Given a int[] containing N elements. The i-th (0-based index) element of array is the number of persons who live near location i.One car can move to one ...
0
votes
1answer
60 views

Question Understanding Simple Algebra With Regards to Computational Complexity

Initial Disclaimer: I decided not to post this on Stack Overflow as my problem lies with understanding the mathematics of this problem, but does not relate to theory at all. I am studying Parallel ...
2
votes
0answers
71 views

Maximizing an algebraic expression using brackets

It's a riddle of sorts: given a list of numbers $\alpha_1 \dots \alpha_n$ and operators $o_1 \dots o_{n-1}$ which can be only $\times\, \mbox{or}\, + $ if the above is a specific algebraic expression ...
2
votes
0answers
42 views

Is there a known algorithm for approximating all the real and imaginary zeros of any well behaved equation of a single variable?

Does there currently exist a general algorithm (or set of algorithms used together) that will approximate all the zeros of any well behaved non-differential equation of a single variable which has a ...
0
votes
1answer
69 views

What is the Mirror/PingPong clamp mode algorithm?

I do programming as a hobby, and in a dynamic system various numerical values inevitably change. Those values can be greater than or less than the expected range, in which case they need to be ...
1
vote
2answers
127 views

How can I optimise the power series calculation of the exponential function?

In an answer to the question Fastest way to calculate $e^x$ upto arbitrary number of decimals? there is a description of a method by which the number of terms needed to calcluate $e^x$ to a given ...
5
votes
5answers
267 views

pandigital rational approximations to the golden ratio and the base of the natural logarithm

Steven Stadnicki suggested in a comment that I post the following as a question. The golden ration $\phi$ is given by $$\phi = \frac{1+\sqrt{5}}{2} \approx 1.618033988.$$ A rational approximation is ...
0
votes
1answer
27 views

Rounding to the nearest term in a geometric progression

Consider the following progression: where i is ith number within the progression. I would like to devise an equation that will round input value to the nearest number from this progression. For ...
1
vote
1answer
45 views

Smallest value of n for two algoritms with a certain running time

If one algorithm has a running time of $100n^2$ and another of $2^n$; how can I find the smallest value of $n$ such that the former is faster than the latter? I could do: $100n^2 < 2^n$ then ...
1
vote
1answer
103 views

Celsius to Fahrenheit back and forth conversion with rounding.

Recently I've encountered some problem with conversion Celsius and Fahrenheit scales. Let's assume that I have value of 44 degrees in Fahrenheit scale, I convert this to the Celsius which gives me ...
4
votes
2answers
173 views

Accounting for changing radius of a paper roll to always unroll the same amount of paper

So I'm building a Post-Turing Machine that's running a 5-state busy beaver. It has a 300ft roll of receipt paper at each end simulating an infinite tape. Hypothetically the tape is divided into ...
0
votes
1answer
40 views

Algorithm for root function $[2^{n-1}]$

I am attempting to convert this function $[2^{n-1}]$ into a root function to return original value. Thus far all my attempts have ended in abject failure. Base : 1 2 3 4 5 6 7 8 9 Result : ...
-3
votes
1answer
63 views

Maximize $f(p)=(k-p)^2+(p-1)^2$

From a computer algorithms analysis (quicksort), its given that $f(p)=(k-p)^2+(p-1)^2$ is maximized when $p=1, p=k$. But how do they get that?
9
votes
5answers
601 views

Algorithms for “solving” $\sqrt{2}$

The very first words out of my mouth need to be this... "Solving" is the wrong term since I am speaking about irrational numbers. I just don't know which word is the correct word... So that can be ...
0
votes
1answer
89 views

Solving this inequality without trial and error

"What is the smallest value of $n$ such that an algorithm whose running time is $100n^2$ runs faster than an algorithm whose running time is $2^n$ on the same machine?" I know the answer is $n = ...
4
votes
1answer
860 views

The trick to proving trigonometric identities

This question is motivated from the following excerpt from Rational Points on Elliptic Curves by Silverman and Tate: $$\cos \theta = \frac{1 - t^2}{1 + t^2}, \sin \theta = \frac{2t}{1+t^2}$$ ...
2
votes
3answers
94 views

Is there any fast way to get the number of a certain day in a week

I'm realy sorry, if this question is a bit stupid... But this is my first time on mathematics stackexchange. Do you guys now for example, how to know the number of monday in a year?
0
votes
2answers
302 views

Universal Formula for Expanding Brackets

I know how to expand brackets such as the following in general, using the foil or crab-claw methods, but my tutor mentioned that there is a universal formula/algorithm for an expansion. E.g Bracket: ...
0
votes
1answer
140 views

Divide N items into M groups with as near equal size as possible

Im trying to split (say) N pink, fluffy balls into M groups as evenly as possible. Eg: ...
-1
votes
1answer
58 views

what is a general algorithm to find a nonempty integer subset that have integers add up to 0?

what is a general algorithm to compute if a set have nonempty integer subset that have integers add up to 0? i would like to know one with the least tries and the proof of it. Example:{−2, −3, 15, ...
0
votes
1answer
74 views

Non-proportional, inverse algorithm

I'm trying to come up with the correct algorithm for a setting on a meter in my app. Basically, I have a value (lets call it 'x') returned from a source which can be in the range of 0 to 30. As x ...
2
votes
2answers
733 views

Take set of values and change scale [duplicate]

I have a large array of variable-integer keypairs. The integer values range from -5 to 5. I'd like to scale that data to a range of 0 to 2. Logically, -5 would become 0, 0 would become 1 and 5 would ...
4
votes
2answers
426 views

Russian Peasant Method for multiplication

What exactly happens with the remainder in this algorithm? I don't understand why it is "dropped". Example: $$\begin{array}{c} \text{Half}&&\text{Double}&\text{Remainder}\\ \hline ...
1
vote
1answer
172 views

Trying to sort the coefficients of the polynomial $(z-a)(z-b)(z-c)…(z-n)$ into a vector

So I have a factored polynomial of the form $(z-a)(z-b)(z-c)\ldots(z-n)$ for $n$ an even positive integer. Thus the coefficient of $z^k$ for $0 \le k < n$ will be the sum of all distinct $n-k$ ...
1
vote
1answer
59 views

Trivial question on an algebraic equation

I am too rusty in algebra. I have as input in a program numbers a and b. I am trying to find them using the bellow relation: ...
0
votes
0answers
52 views

How are these operations the same? How to convert a multiplication in a different form?

I am reading on a specific operation, how it should be done in order to avoid overflow during multiplication. The operation is: $$( A * \text{state} ) \% M;$$ This is susceptible to overflow. The ...
4
votes
1answer
172 views

How to find out if two solutions are equivalent or different?

Given 5 different numbers ($\in \mathbb N$) in a specific brackets pattern like: $$\left(\left(\left(x_1 + x_2 \right) - x_3\right) \times x_4 \right) / x_5 = \text{result}$$ Only the brackets are ...
0
votes
1answer
90 views

Different solutions under distributive and commutative equivalence

Given 5 numbers: $x_1, x_2, x_3, x_4, x_5 \in \mathbb N$ all the 4 operations: $+ - \times /$ a specific brackets pattern: $\left(\left(\left(x_1 + x_2 \right) - x_3\right) \times x_4 \right) / ...
3
votes
2answers
205 views

Can this be solved by induction? (number of ways of cutting a rod into pieces)

I am reading an algorithm example. The example is about Rod cutting. The idea is that a steel rod can either be sold as it is, or be cut into integral pieces and ...
4
votes
2answers
570 views

Upper bound for the partial sum $\sum k \lg k$ via summation?

In this lecture of an introductory class to algorithms (video here, time 74:09), the professor cites the following as an upper bound: $$ \sum_{k=2}^n k \lg k \leq \frac{1}{2} n^2 \lg n - \frac{1}{8} ...
0
votes
2answers
454 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: ...
0
votes
1answer
126 views

Help on understanding the proof for the max subsequence problem

I am trying to understand a proof. The problem is the detection of the maximum continuous subsequence sum problem (i.e. find the subsequence of an array that gives the maximum sum). The ...
6
votes
4answers
1k views

calculating n choose k mod one million

I am working on a programming problem where I need to calculate 'n choose k'. I am using the relation formula $$ {n\choose k} = {n\choose k-1} \frac{n-k+1}{k} $$ so I don't have to calculate huge ...
0
votes
1answer
58 views

Formula to recalculate variables from real numbers range to non-negative range

I'm struggling with this for quite some time now. I'm trying to recalculate values uniformly distributed in real numbers range to numbers in non-negative range. Length of non-negative range can vary ...
4
votes
1answer
88 views

Proving that $n^n \notin O((n+1)!)$

How does one show that $n^n \notin O((n+1)!)$ without using limits? I've recently been trying to prove such results without limits, and this is one case that is still bothering me.
0
votes
1answer
169 views

Need an algebraic formula for this algorithmic problem

I'm not sure if there is a given term for this problem but I'm trying to find the number of iterations required to complete this type of pattern: Consider two patterns/lists: ...