Pages

Sunday, January 29, 2012

Test title

test content

Saturday, July 30, 2011

Fibonacci numbers

Mathematica
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.

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.

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

Merge sort

Will take O(n * log (n)) time, and does not depend on input.

Java

C#

Tuesday, July 26, 2011

Insertion sort

Efficient for small lists, with size less then 30.

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);
 }
}

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));
 }
}