Looking for a particular algorithm for numerical integration

Tag: algorithm,numerical-methods,numerical,numerical-integration

Consider the following differential equation
f(x) = g'(x)
I have a build a code that spits out values of the function f(x) for the variable x, where x goes from 0 to very large.

Now, I'm looking for a scheme that will analyse these values of f(x) in order to determine g(x). Does anybody have any suggestions? The main problem is that if I would calculate g(x) = Integral (f(x) * dx), then I'll end up with just a number (i.e. the area under the graph), but I need to know the actual function of g(x).

I've cross-posted this question here: http://math.stackexchange.com/questions/1326854/looking-for-a-particular-algorithm-for-numerical-integration

Best How To :

numerical integration always return just a number
- if you do not want the number but function instead
- then you can not use numerical integration for this task directly
Polynomial approach
- you can use any approximation/interpolation technique to obtain a polynomial representing f(x)
- then integrate as standard polynomial (just change in exponent and multiplication constant)
- this is not suited for transcendent, periodical or complex shaped functions
- most common approaches is use of L'Grange or Taylor series
- for both you need a parser capable of returning value of f(x) for any given x
algebraic integration
- this is not solvable for any f(x) because we do not know how to integrate everything
- so you would need to program all the rules for integration
- like per-partes,substitutions,Z or L'Place transforms
- and write a solver within string/symbol paradigm
- that is huge amount of work
- may be there are libs or dlls that can do that
- from programs like Derive or Matlab ...

[edit1] As the function f(x) is just a table in form

double f[][2]={ x1,f(x1),x2,f(x2),...xn,f(xn) };
you can create the same table for g(x)=Integral(f(x)) at interval <0,x>

so:

g(x1)=f(x1)*(x1-0)
g(x2)=f(x1)*(x1-0)+f(x2)*(x2-x1)
g(x3)=f(x1)*(x1-0)+f(x2)*(x2-x1)+f(x3)*(x3-x2)
...

this is just a table so if you want actual function you need to convert this to polynomial via L'Grange or any other interpolation...
you can also use DFFT and for the function as set of sin-waves

Understanding Big-Ω (Big-Omega) notation

algorithm,big-o

Big O,Theta or Omega notation all refer to how a solution scales asymptotically as the size of the problem tends to infinity, however, they should really be prefaced with what you are measuring. Usually when one talks about big O(n) one usually means that the worst case complexity is O(n),...

Dynamic programming: how to design algorithm for when there are two factors to consider?

algorithm,optimization,dynamic-programming,frequency

There is no need for Dynamic Programming for this problem. It is a simple sorting problem, with a slight twist. Find frequency / length for each file. This gets you, how frequent is each unit length access for the file. Sort these in descending order since each file is "penalized"...

Use Recursion to get Subsets of an array. C++ and Java give me different results

java,c++,algorithm,recursion,dfs

In the line res.add(temp); temp is a reference. You are adding a reference to the same list (itemList) every time you add it. Try changing it to something list res.add(new ArrayList(temp)); so that it copies the list instead....

Binary Search - Best and worst case

algorithm,data-structures

3. is indeed correct, as you will need to go through the algorithm and terminate at the "worst" stop clause, where the list is empty, needed log(n) iterations. 1. is not correct. The best case is NOT when the first element is the target, it is when the middle element...

How to check whether the letters of a string exist in the given order within another string?

c++,algorithm

You may access out of bound memory while accessing key[counter] causing undefined behaviour. One possible fix is: for (int i = 0; i < s.size(); i++){ if (s[i] == key[counter]){ if(++counter == 5) break; // ^^ ^^^^ ^^^^^ } } or rewrite for as for (int i = 0; i...

Find the shortest path sum in a matrix. Is Dijkstra not optimal for this case?

algorithm,go

Dijkstra should pass, I just make a submission using JAVA, and it took less than a second to complete each task. As I have mentioned, each value in the matrix can go up to 10^9, your solution can encounter a number overflow problem, which can effect the running time. My...

Should checking loop conditions be counted towards total number of comparisons?

c++,algorithm,sorting,c++11

If you look at your inserstion sort As you already put count =1 because as for exits on exit condition of for loop. for same reason then it also make sense that when while loop cancels the count++ inside will not get executed but there was a comparison made. but...

3 X 3 magic square recursively

c++,algorithm,math,recursion

Basically, you are finding all permutations of the array using a recursive permutation algorithm. There are 4 things you need to change: First, start your loop from pos, not 0 Second, swap elements back after recursing (backtracking) Third, only test once you have generated each complete permutation (when pos =...

Given length L find the shortest string formed only of as & bs >= L such that adding some character (Either a or b) doesn't produce a new palindrome

string,algorithm,palindrome

Here are my results so far: L=1-7: "aabbaba" -> "aabbabaa" (or the mirror, confirming your result) L=8: "aaabbaba" -> "aaabbabaa" (or the mirror) L=9: "aaaabbbaba" -> "aaaabbbabaa" (or the mirror) All futher L can be solved just by prefixing an additional a to the starting string....

How can I declare a counter inside of my recursive function? (Additive Persistence: Coderbyte)

javascript,algorithm,recursion

I'm going to extend @georg's answer and provide a full implementation var additivePersistance = (function () { function sumOfDigits (n) { var ret = 0; n.toString().split('').forEach(function (i) { ret += parseInt(i, 10); }); return ret; } return function additivePersistance (n) { if (n < 10) { return 0; } return...

strcmp performance in C

c,string,algorithm,data-structures

Yes, this is in O(n) in the average and worst case, where n is the length of the shorter of both given strings. You could also express that as O(min(m,n)) with m and n being the lengths of both strings, respectively. But no, O(n) doesn't mean that it needs exactly...

Getting Wrong Answer in “Longest non regular parentheses sub-sequence ”codechef june cook off

algorithm

See I know you will feel bad when I will tell you what is wrong in your answer. But the only thing wrong is you using gets(). Its 2015 no one uses it. I changed that to a scanf statement i.e delete this part of your code and get(s); get(s);...

Recursive algorithm that returns a bool when checking if array[i] == i (must be O(log n))

c++,arrays,algorithm,recursion

Do a regular binary search but with the (array[i] == i) condition instead of searching for a particular value. If (array[i] > i) move left else move right Of course this requires the values to be sorted, but your example indicates that is the case....

Remove smallest non-unique value from vector

c++,algorithm,c++11,unique

(Am adding an additional answer, since 1) the focus of the first answer was using ready STL components, and 2) Howard Hinnant raised some interesting points since.) Thanks to Howard Hinnant for the principle of benchmarking the different approaches (as well as a very unique solution)! It has led to...

Update minimum spanning tree if edge is added

algorithm,graph,tree,runtime,big-o

Don't know if your algorithm is correct, but it doesn't seem O(|V|) at least, because getting the "smallest edge not in T" of a vertex cannot be done in O(1). The most usual way to add an edge e=(u, v) into a MST T is: Run a BFS in T...

Best way to extract ODD digits from a binary number

algorithm,bit-manipulation

I would go with performing Arithmetic Right Shift(till the length of the binary number) two at a time. This >> used in my logic is for arithmetic shift. (Note: In C language, right shifts may or may not be arithmetic!) Like, int count=0; bit=extractLastbit(binary_representation_of_the_number); while(count!=binaryLength){ // binaryLength is the length...

How to apply ordering to a Scala Priority Queue?

algorithm,scala,priority-queue

If your elements are Ints, the easiest way to define such an Ordering is by taking a negative of the elements which should be ordered in reverse. You can create the Ordering, using methods provided by the object Ordering, and pass it to the PriotityQueue either explicitly: // I'm using...

Project Euler # 5; this solution works - but why?

c++,algorithm

Your logic does not work if(i%(ans%i)==0)ans*=(i/(ans%i)); else ans*=i; For example, if ans = 10 and i = 14, so, the lcm should be 70, but in your code, it is 140. The reason is, between ans and i , there are common divisors, but your code cannot detect that. For...

Travels using graph

c++,algorithm,graph

Here is the graph I propose: Two kinds of vertices: departure vertex: airport+departure time arrival vertex: airport + arrival time. Two kind of edges: flight edge: from a departure vertex to an arrival vertex wait edge: from an arrival vertex to a departure vertex of later time in the same...

Given a sorted array and a parameter k, find the count of sum of two numbers greater than or equal to k

c++,arrays,algorithm,sum

There exists a rather simple O(n) approach using the so-called "two pointers" or "two iterators" approach. The key idea is to have two iterators (not necessarily C++ iterators, indices would do too) running on the same array so that if first iterator points to value x, then the second iterator...

Vector Merge Algorithm C++

c++,algorithm

Try this, it worked for me with your example matrix. It looks like a lot of code, but there are functions just for the example and for debugging purpose. void disp( const std::vector< int >& a ) { for ( const auto item : a ) { std::cout << item;...

Ranking with time weighting

python,algorithm,sorting,math

To clarify @Dan Getz and add @collapsar answer I will add the following: Dan's Formula is correct: (score1 * weight1 + ... + scoreN * weightN) / (weight1 + ... + weightN) The beauty of the weighted average is you get to choose the weights! So we choose days since...

Update minimum spanning tree if edge is removed

algorithm,graph,tree,runtime,big-o

Since everything is still connected and only one edge has been removed, then most (and maybe all) of the spanning tree remains the same. Attempt to construct the same minimum spanning tree, and if the edge that was removed was part of the spanning tree, grab the next smallest edge...

Reverse ^ operator for decryption

c,algorithm,security,math,encryption

This is not a power operator. It is the XOR operator. The thing that you notice for the XOR operator is that x ^ k ^ k == x. That means that your encryption function is already the decryption function when called with the same key and the ciphertext instead...

How to reduce time to find the n-th place from consecutive digits number for less than 1 second

php,algorithm,digits

What's important to realize is that it's easy to take big steps: 1 digit numbers: 123456789 - 9 * 1 digit 2 digit numbers: 101112...9899 - 90 * 2 digits 3 digit numbers: 100101102...998999 - 900 * 3 digits 4 digit numbers: ... Now you can do a recursive solution...

Knapsack with unbounded items

algorithm,dynamic-programming,knapsack-problem

One possibility would be to provide a suitable number of multiplicities of the items. For item i, there can be at most m_i := K / w_i choices of that item, where K denotes the knapsack capacity and w_i denotes the weight of the i-th item. Furthermore, for each weight...

Longest Increasing Subsequence code in O(N)?

python,algorithm,time-complexity,longest-substring

It's O(N) 'why to use DP of O(N2)' : You don't need to for this problem. Note, though, that you take advantage of the fact that your sequence tokens (letters) are finite - so you can set up a list to hold all the possible starting values (26) and...

Algorithmic big o order of growth code

algorithm,discrete-mathematics

The loops in fact only go up to the cube root of N. (i^3 < n, etc.) The 3 nested loops of this length, give O(cube root of N, cubed). This O(N) Of note, if you were correct and they each went to one third of N, then cubing this...

algorithm to get all combinations of splitting up N items into K bins

algorithm,recursion,permutation

A common approach is as follows. If you have, say, K bins, then add K-1 special values to your initial array. I will use the -1 value assuming that it never occurs in the initial array; you can choose a different value. So for your example the initial array becomes...

Recursive solution doesn't iterate correctly

ruby,algorithm,search,recursion

The first time you enter the adjacencies[to_append].each, you immediately return from the method, therefore the loop will never be executed more than once. You need to return a list of phone numbers instead of just a single phone number build that list somehow in your recursive call ...

Genetic Algorithm - convergence

java,algorithm,function,genetic-programming,convergence

I don't have the time to dig into your code but I'll try to answer from what I remember on GAs: Sometimes I will give it points that will never produce a function, or will sometimes produce a function. It can even depend on how deep the initial trees are....

C: sorted input serials

c,algorithm

The merge function is wrong, you did not consider when some part of a or b has leftover elements. void merge(int * a, int ac, int * b, int bc, int * out) { int i = 0, j = 0; while (i < ac && j < bc) {...

Removing a prior sample while using Welford's method for computing single pass variance

algorithm,math,statistics,variance,standard-deviation

Given the forward formulas Mk = Mk-1 + (xk – Mk-1) / k Sk = Sk-1 + (xk – Mk-1) * (xk – Mk), it's possible to solve for Mk-1 as a function of Mk and xk and k: Mk-1 = Mk - (xk - Mk) / (k - 1)....

Determining if a graph has a cycle without using DFS

algorithm,graph,cycle,dfs

If and only if, at some point during kahn's algorithm has no source to choose (and the remaining graph is still none empty), there is a cycle Proof: Direction1 <--: If there is a cycle, let it be v1->v2->v3->vk->v1. At each step of the algorithm, none of v1,v2,...,vk is a...

Does there exist an algorithm for iterating through all strings that conform to a particular regex?

c#,regex,algorithm

Let's say the domain is as following String domain[] = { a, b, .., z, A, B, .. Z, 0, 1, 2, .. 9 }; Let's say the password size is 8 ArrayList allCombinations = getAllPossibleStrings2(domain,8); This is going to generate SIZE(domain) * LENGTH number of combinations, which is in...

Identify that a string could be a datetime object

python,regex,algorithm,python-2.7,datetime

What about fuzzyparsers: Sample inputs: jan 12, 2003 jan 5 2004-3-5 +34 -- 34 days in the future (relative to todays date) -4 -- 4 days in the past (relative to todays date) Example usage: >>> from fuzzyparsers import parse_date >>> parse_date('jun 17 2010') # my youngest son's birthday datetime.date(2010,...

Javascript: Detailed differences between !variable and variable == false?

javascript,algorithm

undefined is not a boolean value so when you use ! operator, your value will be converted to boolean at first. but == operator just checking your values. so if you want to get true from undefined == false you should do it like Boolean(undefined) == false ? 't' :...

Hungarian algorithm in PHP with multiple assignments

php,algorithm,assign,subgraph,pairing-heap

So I finally found a valid way to achieve what was described in before. The solution: We make a column for each slot that is possibly given away. A cours has a amount of slots. We should have a number of columns, which is the sum of each amount of...

Looking for a particular algorithm for numerical integration

algorithm,numerical-methods,numerical,numerical-integration

numerical integration always return just a number if you do not want the number but function instead then you can not use numerical integration for this task directly Polynomial approach you can use any approximation/interpolation technique to obtain a polynomial representing f(x) then integrate as standard polynomial (just change...

Algorithm for [inclusive/exclusive]_scan in parallel proposal N3554

c++,algorithm,parallel-processing,c++14

Parallel prefix sum is a classical distributed programming algorithm, which elegantly uses a reduction followed by a distribution (as illustrated in the article). The key observation is that you can compute parts of the partial sums before you know the leading terms.

Explain the time complexity of these grouping functions

c++,algorithm,inheritance,time-complexity

The first is supposedly in O(M*logN) time, where M is the size of the list, and N = number of concrete derived classes of Base It's not though. unordered_map is a hashtable, lookup and insertion have constant complexity on average. So the first is still O(M). Just with more...

How to generate all partitions of a set

algorithm,set,combinatorics,backtracking

You can try the recursive answer if your set is not to big (or else use stack) : The principle is the following, you have a function that give back : rec_func(SET) = List of List of Set And work as follow : rec_func(SET) = if SET = {empty}: //...

Disconnect all vertices in a graph - Algorithm

algorithm,graph

IIUC, this is the classic Minimum Vertex Cover problem, which is, unfortunately, NP Complete. Fortunately, the most intuitive and greedy possible algorithm is as good as it gets in this case....

Calculating completion time of scheduled dependent tasks

python,algorithm

Assume task 0 finishes at day 0. Add a new column to your table, "completion day". Go down the list of tasks, add the duration of the current task onto the completion day of the task it is dependent on. Store that as the current task's completion day. Find the...

How to print the right hemisphere of a square matrix

c++,algorithm,matrix

I think this should work for square matrices: void printHemisphere(int matrix[N][M], int n, int m) { int mid = n / 2; for(int i = 1; i < mid; i++) { for (int j = n - i; j < m; ++j) { std::cout << matrix[i][j] << " "; }...

How to give mathemarical proof or support my answer through reasoning as a general case?

algorithm

This would be a hard real-time system - if a deadline is missed then a patient might die. As such, Algorithm B is the preferred algorithm because you can design the hardware around the n^2 worst case, whereas with Algorithm A the hardware must account for the n^4 worst case...

Lengths of cycles in random sequence

c#,arrays,algorithm,random,cycle

What you are doing is generating a random permutation of size count. Then you check the properties of the permutation. If your random number generator is good, then you should observe the statistics of random permutations. The average number of cycles of length k is 1/k, for k<count. On average,...

create specific permutation of a list in python [closed]

python,algorithm,permutation

l = [1,'a',12,'b','poppy'] def p(l,t): return [l[i-1] for i in t] print(p(l,(3,4,5,2,1))) [12, 'b', 'poppy', 'a', 1] indexing is 0 based so if you actually wanted to use the indexes for a 5 element list it would be (2,3,4,1,0) and [l[i] for i in t]...

What is this algorithm mapping coordinates to numbers called?

algorithm,coordinates,coordinate-systems,coordinate

So here's my question: does this algorithm exists already? Has it a name? This mapping is called the Z-order curve or Morton code: In mathematical analysis and computer science, Z-order, Morton order, or Morton code is a function which maps multidimensional data to one dimension while preserving locality of...