Search Results

Search found 14 results on 1 pages for 'exponentiation'.

Page 1/1 | 1 

• Efficient implementation of natural logarithm (ln) and exponentiation

  - by Donotalo

  Basically, I'm looking for implementation of log() and exp() functions provided in C library <math.h>. I'm working with 8 bit microcontrollers (OKI 411 and 431). I need to calculate Mean Kinetic Temperature. The requirement is that we should be able to calculate MKT as fast as possible and with as little code memory as possible. The compiler comes with log() and exp() functions in <math.h>. But calling either function and linking with the library causes the code size to increase by 5 Kilobytes, which will not fit in one of the micro we work with (OKI 411), because our code already consumed ~12K of available ~15K code memory. The implementation I'm looking for should not use any other C library functions (like pow(), sqrt() etc). This is because all library functions are packed in one library and even if one function is called, the linker will bring whole 5K library to code memory.

  Read the article

• What is the justification for Python's power operator associating to the right?

  - by Pieter Müller

  I am writing code to parse mathematical expression strings, and noticed that the order in which chained power operators are evaluated in Python differs from the order in Excel. From http://docs.python.org/reference/expressions.html: "Thus, in an unparenthesized sequence of power and unary operators, the operators are evaluated from right to left (this does not constrain the evaluation order for the operands): -1*2 results in -1."* This means that, in Python: 2**2**3 is evaluated as 2**(2**3) = 2**8 = 256 In Excel, it works the other way around: 2^2^3 is evaluated as (2^2)^3 = 4^3 = 64 I now have to choose an implementation for my own parser. The Excel order is easier to implement, as it mirrors the evaluation order of multiplication. I asked some people around the office what their gut feel was for the evaluation of 2^2^3 and got mixed responses. Does anybody know of any good reasons or conciderations in favour of the Python implementation? And if you don't have an answer, please comment with the result you get from gut feel - 64 or 256?

  Read the article

• What does the ^ operator do in Java?

  - by joroj

  What function does the "^" operator serve in Java? When I try this: int a = 5^n; ...it gives me: for n = 5, returns 0 for n = 4, returns 1 for n = 6, returns 3 ...so I guess it doesn't indicate exponentiation. But what is it then?

  Read the article

• Tail-recursive pow() algorithm with memoization?

  - by Dan

  I'm looking for an algorithm to compute pow() that's tail-recursive and uses memoization to speed up repeated calculations. Performance isn't an issue; this is mostly an intellectual exercise - I spent a train ride coming up with all the different pow() implementations I could, but was unable to come up with one that I was happy with that had these two properties. My best shot was the following: def calc_tailrec_mem(base, exp, cache_line={}, acc=1, ctr=0): if exp == 0: return 1 elif exp == 1: return acc * base elif exp in cache_line: val = acc * cache_line[exp] cache_line[exp + ctr] = val return val else: cache_line[ctr] = acc return calc_tailrec_mem(base, exp-1, cache_line, acc * base, ctr + 1) It works, but it doesn't memorize the results of all calculations - only those with exponents 1..exp/2 and exp.

  Read the article

• How to implement square root and exponentiation on arbitrary length numbers?

  - by tomp

  I'm working on new data type for arbitrary length numbers (only non-negative integers) and I got stuck at implementing square root and exponentiation functions (only for natural exponents). Please help. I store the arbitrary length number as a string, so all operations are made char by char. Please don't include advices to use different (existing) library or other way to store the number than string. It's meant to be a programming exercise, not a real-world application, so optimization and performance are not so necessary. If you include code in your answer, I would prefer it to be in either pseudo-code or in C++. The important thing is the algorithm, not the implementation itself. Thanks for the help.

  Read the article

• How to solve linear recurrences involving two functions?

  - by Aditya Bahuguna

  Actually I came across a question in Dynamic Programming where we need to find the number of ways to tile a 2 X N area with tiles of given dimensions.. Here is the problem statement Now after a bit of recurrence solving I came out with these. F(n) = F(n-1) + F(n-2) + 2G(n-1), and G(n) = G(n-1) + F(n-1) I know how to solve LR model where one function is there.For large N as is the case in the above problem we can do the matrix exponentiation and achieve O(k^3log(N)) time where k is the minimum number such that for all km F(n) does not depend on F(n-k). The method of solving linear recurrence with matrix exponentiation as it is given in that blog. Now for the LR involving two functions can anyone suggest an approach feasible enough for large N.

  Read the article

• Would it be a good idea to work on letting people add arrays of numbers in javascript?

  - by OneThreeSeven

  I am a very mathematically oriented programmer, and I happen to be doing a lot of java script these days. I am really disappointed in the math aspects of javascript: the Math object is almost a joke because it has so few methods you can't use ^ for exponentiation the + operator is very limited, you cant add array's of numbers or do scalar multiplication on arrays Now I have written some pretty basic extensions to the Math object and have considered writing a library of advanced Math features, amazingly there doesn't seem to be any sort of standard library already out even for calculus, although there is one for vectors and matricies I was able find. The notation for working with vectors and matricies is really bad when you can't use the + operator on arrays, and you cant do scalar multiplication. For example, here is a hideous expression for subtracting two vectors, A - B: Math.vectorAddition(A,Math.scalarMultiplication(-1,B)); I have been looking for some kind of open-source project to contribute to for awhile, and even though my C++ is a bit rusty I would very much like to get into the code for V8 engine and extend the + operator to work on arrays, to get scalar multiplication to work, and possibly to get the ^ operator to work for exponentiation. These things would greatly enhance the utility of any mathematical javascript framework. I really don't know how to get involved in something like the V8 engine other than download the code and start working on it. Of course I'm afraid that since V8 is chrome specific, that without browser cross-compatibility a fundamental change of this type is likely to be rejected for V8. I was hoping someone could either tell me why this is a bad idea, or else give me some pointers about how to proceed at this point to get some kind of approval to add these features. Thanks!

  Read the article

• Why does Java's hashCode() in String use 31 as a multiplier?

  - by jacobko

  In Java, the hash code for a String object is computed as s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] using int arithmetic, where s[i] is the ith character of the string, n is the length of the string, and ^ indicates exponentiation. Why is 31 used as a multiplier? I understand that the multiplier should be a relatively large prime number. So why not 29, or 37, or even 97?

  Read the article

• Cuda driver, CPU/GPU performances issue

  - by elect

  I implemented a RNS Montgomery exponentiation in Cuda and on cpu for comparison. Everything nice everything fine. It runs on just one SM. However I am going to tell you some strange regression in both cpu/gpu performances. During the devoloping, about two month ago, I was using Cuda 5 preview on Ubuntu 11.04 64b. In this time, I reach the following performances: cpu 460ms gpu 120ms Then one day when I turn on the pc, the graphical environment didnt start. I dont know which was the problem, however I switched to the console and installed again the Cuda driver. At the following boot performances changed: cpu 310ms gpu 80ms I was like Q.Q...uhm ok, nice to see this, but I was wondering how that could be possible However, I went then in holiday for 10 days and I continued developing and optimizing on my notebook (but not the same part of the code, some additional stuff) When I was back, I just updated the source files, and performances came back to 460/120ms.. I couldnt believe it, I tried to install Cuda 5 RC, updating the video driver too... nothing changed... I checked Debug/Release, Cuda computability, but the problem seems being somewhere else.. Looking around the net I found this, I am pretty sure it must have something to do with the driver, because the performance change affected both cpu and gpu Do you have some tips/ideas/suggestions?

  Read the article

• why C clock() returns 0

  - by eddy ed

  I've got something like this: clock_t start, end; start=clock(); something_else(); end=clock(); printf("\nClock cycles are: %d - %d\n",start,end); and I always get as an output "Clock cycles are: 0 - 0" Any idea why this happens? (Just to give little detail, the something_else() function performs a left-to-right exponentiation using montgomery represantation, moreover I don't know for certain that the something_else() function does indeed take some not negligible time.) This is on Linux. The result of uname -a is: Linux snowy.*****.ac.uk 2.6.32-71.el6.x86_64 #1 SMP Fri May 20 03:51:51 BST 2011 x86_64 x86_64 x86_64 GNU/Linux

  Read the article

• java.math.BigInteger pow(exponent) question

  - by Jan Kraus

  Hi, I did some tests on pow(exponent) method. Unfortunately, my math skills are not strong enough to handle the following problem. I'm using this code: BigInteger.valueOf(2).pow(var); Results: var | time in ms 2000000 | 11450 2500000 | 12471 3000000 | 22379 3500000 | 32147 4000000 | 46270 4500000 | 31459 5000000 | 49922 See? 2,500,000 exponent is calculated almost as fast as 2,000,000. 4,500,000 is calculated much faster then 4,000,000. Why is that? To give you some help, here's the original implementation of BigInteger.pow(exponent): public BigInteger pow(int exponent) { if (exponent < 0) throw new ArithmeticException("Negative exponent"); if (signum==0) return (exponent==0 ? ONE : this); // Perform exponentiation using repeated squaring trick int newSign = (signum<0 && (exponent&1)==1 ? -1 : 1); int[] baseToPow2 = this.mag; int[] result = {1}; while (exponent != 0) { if ((exponent & 1)==1) { result = multiplyToLen(result, result.length, baseToPow2, baseToPow2.length, null); result = trustedStripLeadingZeroInts(result); } if ((exponent >>>= 1) != 0) { baseToPow2 = squareToLen(baseToPow2, baseToPow2.length, null); baseToPow2 = trustedStripLeadingZeroInts(baseToPow2); } } return new BigInteger(result, newSign); }

  Read the article

• Round-twice error in .NET's Double.ToString method

  - by Jeppe Stig Nielsen

  Mathematically, consider for this question the rational number 8725724278030350 / 2**48 where ** in the denominator denotes exponentiation, i.e. the denominator is 2 to the 48th power. (The fraction is not in lowest terms, reducible by 2.) This number is exactly representable as a System.Double. Its decimal expansion is 31.0000000000000'49'73799150320701301097869873046875 (exact) where the apostrophes do not represent missing digits but merely mark the boudaries where rounding to 15 resp. 17 digits is to be performed. Note the following: If this number is rounded to 15 digits, the result will be 31 (followed by thirteen 0s) because the next digits (49...) begin with a 4 (meaning round down). But if the number is first rounded to 17 digits and then rounded to 15 digits, the result could be 31.0000000000001. This is because the first rounding rounds up by increasing the 49... digits to 50 (terminates) (next digits were 73...), and the second rounding might then round up again (when the midpoint-rounding rule says "round away from zero"). (There are many more numbers with the above characteristics, of course.) Now, it turns out that .NET's standard string representation of this number is "31.0000000000001". The question: Isn't this a bug? By standard string representation we mean the String produced by the parameterles Double.ToString() instance method which is of course identical to what is produced by ToString("G"). An interesting thing to note is that if you cast the above number to System.Decimal then you get a decimal that is 31 exactly! See this Stack Overflow question for a discussion of the surprising fact that casting a Double to Decimal involves first rounding to 15 digits. This means that casting to Decimal makes a correct round to 15 digits, whereas calling ToSting() makes an incorrect one. To sum up, we have a floating-point number that, when output to the user, is 31.0000000000001, but when converted to Decimal (where 29 digits are available), becomes 31 exactly. This is unfortunate. Here's some C# code for you to verify the problem: static void Main() { const double evil = 31.0000000000000497; string exactString = DoubleConverter.ToExactString(evil); // Jon Skeet, http://csharpindepth.com/Articles/General/FloatingPoint.aspx Console.WriteLine("Exact value (Jon Skeet): {0}", exactString); // writes 31.00000000000004973799150320701301097869873046875 Console.WriteLine("General format (G): {0}", evil); // writes 31.0000000000001 Console.WriteLine("Round-trip format (R): {0:R}", evil); // writes 31.00000000000005 Console.WriteLine(); Console.WriteLine("Binary repr.: {0}", String.Join(", ", BitConverter.GetBytes(evil).Select(b => "0x" + b.ToString("X2")))); Console.WriteLine(); decimal converted = (decimal)evil; Console.WriteLine("Decimal version: {0}", converted); // writes 31 decimal preciseDecimal = decimal.Parse(exactString, CultureInfo.InvariantCulture); Console.WriteLine("Better decimal: {0}", preciseDecimal); // writes 31.000000000000049737991503207 } The above code uses Skeet's ToExactString method. If you don't want to use his stuff (can be found through the URL), just delete the code lines above dependent on exactString. You can still see how the Double in question (evil) is rounded and cast.

  Read the article

• Use QuickCheck by generating primes

  - by Dan

  Background For fun, I'm trying to write a property for quick-check that can test the basic idea behind cryptography with RSA. Choose two distinct primes, p and q. Let N = p*q e is some number relatively prime to (p-1)(q-1) (in practice, e is usually 3 for fast encoding) d is the modular inverse of e modulo (p-1)(q-1) For all x such that 1 < x < N, it is always true that (x^e)^d = x modulo N In other words, x is the "message", raising it to the eth power mod N is the act of "encoding" the message, and raising the encoded message to the dth power mod N is the act of "decoding" it. (The property is also trivially true for x = 1, a case which is its own encryption) Code Here are the methods I have coded up so far: import Test.QuickCheck -- modular exponentiation modExp :: Integral a => a -> a -> a -> a modExp y z n = modExp' (y `mod` n) z `mod` n where modExp' y z | z == 0 = 1 | even z = modExp (y*y) (z `div` 2) n | odd z = (modExp (y*y) (z `div` 2) n) * y -- relatively prime rPrime :: Integral a => a -> a -> Bool rPrime a b = gcd a b == 1 -- multiplicative inverse (modular) mInverse :: Integral a => a -> a -> a mInverse 1 _ = 1 mInverse x y = (n * y + 1) `div` x where n = x - mInverse (y `mod` x) x -- just a quick way to test for primality n `divides` x = x `mod` n == 0 primes = 2:filter isPrime [3..] isPrime x = null . filter (`divides` x) $ takeWhile (\y -> y*y <= x) primes -- the property prop_rsa (p,q,x) = isPrime p && isPrime q && p /= q && x > 1 && x < n && rPrime e t ==> x == (x `powModN` e) `powModN` d where e = 3 n = p*q t = (p-1)*(q-1) d = mInverse e t a `powModN` b = modExp a b n (Thanks, google and random blog, for the implementation of modular multiplicative inverse) Question The problem should be obvious: there are way too many conditions on the property to make it at all usable. Trying to invoke quickCheck prop_rsa in ghci made my terminal hang. So I've poked around the QuickCheck manual a bit, and it says: Properties may take the form forAll <generator> $ \<pattern> -> <property> How do I make a <generator> for prime numbers? Or with the other constraints, so that quickCheck doesn't have to sift through a bunch of failed conditions? Any other general advice (especially regarding QuickCheck) is welcome.

  Read the article

• Repeated Squaring - Matrix Multiplication using NEWMAT

  - by Dinakar Kulkarni

  I'm trying to use the repeated squaring algorithm (using recursion) to perform matrix exponentiation. I've included header files from the NEWMAT library instead of using arrays. The original matrix has elements in the range (-5,5), all numbers being of type float. # include "C:\User\newmat10\newmat.h" # include "C:\User\newmat10\newmatio.h" # include "C:\User\newmat10\newmatap.h" # include <iostream> # include <time.h> # include <ctime> # include <cstdlib> # include <iomanip> using namespace std; Matrix repeated_squaring(Matrix A, int exponent, int n) //Recursive function { A(n,n); IdentityMatrix I(n); if (exponent == 0) //Matrix raised to zero returns an Identity Matrix return I; else { if ( exponent%2 == 1 ) // if exponent is odd return (A * repeated_squaring (A*A, (exponent-1)/2, n)); else //if exponent is even return (A * repeated_squaring( A*A, exponent/2, n)); } } Matrix direct_squaring(Matrix B, int k, int no) //Brute Force Multiplication { B(no,no); Matrix C = B; for (int i = 1; i <= k; i++) C = B*C; return C; } //----Creating a matrix with elements b/w (-5,5)---- float unifRandom() { int a = -5; int b = 5; float temp = (float)((b-a)*( rand()/RAND_MAX) + a); return temp; } Matrix initialize_mat(Matrix H, int ord) { H(ord,ord); for (int y = 1; y <= ord; y++) for(int z = 1; z<= ord; z++) H(y,z) = unifRandom(); return(H); } //--------------------------------------------------- void main() { int exponent, dimension; cout<<"Insert exponent:"<<endl; cin>>exponent; cout<< "Insert dimension:"<<endl; cin>>dimension; cout<<"The number of rows/columns in the square matrix is: "<<dimension<<endl; cout<<"The exponent is: "<<exponent<<endl; Matrix A(dimension,dimension),B(dimension,dimension); Matrix C(dimension,dimension),D(dimension,dimension); B= initialize_mat(A,dimension); cout<<"Initial Matrix: "<<endl; cout<<setw(5)<<setprecision(2)<<B<<endl; //----------------------------------------------------------------------------- cout<<"Repeated Squaring Result: "<<endl; clock_t time_before1 = clock(); C = repeated_squaring (B, exponent , dimension); cout<< setw(5) <<setprecision(2) <<C; clock_t time_after1 = clock(); float diff1 = ((float) time_after1 - (float) time_before1); cout << "It took " << diff1/CLOCKS_PER_SEC << " seconds to complete" << endl<<endl; //--------------------------------------------------------------------------------- cout<<"Direct Squaring Result:"<<endl; clock_t time_before2 = clock(); D = direct_squaring (B, exponent , dimension); cout<<setw(5)<<setprecision(2)<<D; clock_t time_after2 = clock(); float diff2 = ((float) time_after2 - (float) time_before2); cout << "It took " << diff2/CLOCKS_PER_SEC << " seconds to complete" << endl<<endl; } I face the following problems: The random number generator returns only "-5" as each element in the output. The Matrix multiplication yield different results with brute force multiplication and using the repeated squaring algorithm. I'm timing the execution time of my code to compare the times taken by brute force multiplication and by repeated squaring. Could someone please find out what's wrong with the recursion and with the matrix initialization? NOTE: While compiling this program, make sure you've imported the NEWMAT library. Thanks in advance!

  Read the article

1