test content
A hit of dopamine
Crafting exhibits of desired behav...
Sunday, January 29, 2012
Saturday, July 30, 2011
Fibonacci numbers
Mathematica
Note, that this implementation exists. Algorithm is:
Java
In Java, we have arbitrarily large integers and decimals, but prebuilt classes lack the functionality (it's a shame). For example we can not easily take root of 5. To do this, we would need to use a library like JScience or write Newton approximation method (what can be quite error prone process).
C#
In C#, there is no arbitrarily large decimals. It does have class decimal (with 28-29 significant digits), but assuming that Math class supports it, is just asking too much (it's a shame). But thumbs up, for it at least has BigInteger.
Note, that this implementation exists. Algorithm is:
Fibonacci[n_] := Round[GoldenRatio^n/Sqrt[5]]
Be aware, that this formula:
can not be trivially applied in other languages.
In Java, we have arbitrarily large integers and decimals, but prebuilt classes lack the functionality (it's a shame). For example we can not easily take root of 5. To do this, we would need to use a library like JScience or write Newton approximation method (what can be quite error prone process).
C#
In C#, there is no arbitrarily large decimals. It does have class decimal (with 28-29 significant digits), but assuming that Math class supports it, is just asking too much (it's a shame). But thumbs up, for it at least has BigInteger.
Labels:
algorithms,
BigDecimal,
BigInteger,
Fibonacci numbers
Thursday, July 28, 2011
Binary search
Java
In java, Collections/Arrays class contains binary search.
Collections.binarySearch(list, key); Arrays.binarySearch(array, key);My naive generic implementation is recursive and ignores the fact, that I should use ListIterator for data structures, that do not have random access (ex. LinkedList).
C#
In C#, list itself and Arrays class contains binary search.
list.BinarySearch(key); Array.BinarySearch(array, key);My naive Java implementation translated to C#.
Mathematica
In mathematica, Combinatorica library contains binary search.
BinarySearch[list, key]
Wednesday, July 27, 2011
Tuesday, July 26, 2011
Insertion sort
Efficient for small lists, with size less then 30.
Special cases are:
Java
C#
Special cases are:
- if list is almost sorted, it will be near linear time
- if sorted list is reversed, it will be quadratic time
Java
C#
Sunday, September 13, 2009
Euler Problem 49 solution
Time (s): ~0.002
package margusmartseppcode.From_40_to_49; import java.util.Arrays; public class Problem_49 { // Call only if: (n>0&&(i%2==0||i%3==0||i%5==0||i%7==0)) static boolean isPrimeS(final int n) { final int r = (int) Math.floor(Math.sqrt(n)); for (int f = 5; f <= r; f += 6) if (n % f == 0 || n % (f + 2) == 0) return false; return true; } static boolean isPerm(char[] a, char[] b) { if (a.length != b.length) return false; Arrays.sort(a); Arrays.sort(b); return Arrays.equals(a, b); } static boolean arePerms(int... n) { if (n.length == 0) return true; for (int i = 1; i < n.length; i++) if (!isPerm(("" + n[i - 1]).toCharArray(), ("" + n[i]) .toCharArray())) return false; return true; } static boolean arePrimes(int... n) { for (int i : n) if (!isPrimeS(i)) return false; return true; } public static void main(String[] args) { int a, b, c; a = b = c = 0; for (a = 1489;; a += 2) { if (a % 3 == 0 || a % 5 == 0 || a % 7 == 0) continue; b = a + 3330; c = a + 6660; if (arePrimes(a, b, c)) if (arePerms(a, b, c)) break; } System.out.println("" + a + b + c); } }
Labels:
Euler Problem 40-49,
permutation,
prime numbers
Euler Problem 48 solution
Time (s): ~0.034
package margusmartseppcode.From_40_to_49; public class Problem_48 { public static void main(String[] args) { long result = 0, d10 = 10000000000L; for (long u = 1, tmp = u; u <= 1000; result += tmp, ++u, tmp = u) for (long v = 1; v < u; ++v) tmp = (tmp * u) % d10; System.out.println(result % d10); } }Time (s): ~0.224
package margusmartseppcode.From_40_to_49; import java.math.BigInteger; public class Problem_48 { // Note: i = 2 !!! public static void main(String[] args) { BigInteger num = BigInteger.ONE; for (int i = 2; i < 1000; i++) num = num.add(BigInteger.valueOf(i).pow(i)); String result = num.toString(); System.out.println(result.substring(result.length() - 10)); } }
Labels:
BigInteger,
Euler Problem 40-49,
factorials
Subscribe to:
Posts (Atom)