Volume of Tetrahedron From Length of Edges

Calculating volume of tetrahedron from its coordinates is easy. But, finding its volume from its edge-lengths made me to scratch my head. 

After googling out a lot, I found this Piero della Francesca’s Tetrahedron Formula. The painter Piero della Francesca (who died in 1492) also studied mathematics, gave the formula for volume of a general tetrahedron with edges a,b,c,d,e,f, taken in opposite pairs (a,f), (b,e), (c,d).

     _________a_________      _________f_________
     \                 /      \                 /
     \ \             / /      \ \             / /
      \  \e       d/  /        \  \e       d/  /
       \   \     /   /          \   \     /   /
        \    \ /    /            \    \ /    /
        c\    |    /b            c\    |    /b
          \   |   /                \   |   /
           \  |f /                  \  |a /
            \ | /                    \ | /
             \|/                      \|/

Letting A,B,..,F denote the squares of these respective edge lengths, his formula was

144 V^2  = - ABC - ADE - BDF - CEF + ACD + BCD + ABE + BCE
           + BDE + CDE + ABF + ACF + ADF + CDF + AEF + BEF
           - CCD - CDD - BBE - BEE - AAF - AFF

for first tetrahedron

and,

144 V^2  = - ABD - ACE - BCF - DEF + ACD + BCD + ABE + BCE
           + BDE + CDE + ABF + ACF + ADF + CDF + AEF + BEF
           - CCD - CDD - BBE - BEE - AAF - AFF 

for the second possible tetrahedron.

Notice edges a and f are swapped to form second tetrahedron from first. Hence we have to take care of the length of sides to use correct formula. For solving the problem mentioned on CodeChef second formula can be used taking the input in the order of  a,b,c,d,e,f.
The surface area can be easily calculated by summing area of all three triangle which can be calculated using Heron’s formula.

Finding Number of Coprimes Less Than Certain Number

(Coprimes of n less than m)

Calculating coprimes of a number less than that number i.e. totient function of a number is easy by some easy tricks.

Suppose we are given a numbers n & m such that m<n and we have to calculate coprimes of n which are less than n. This can also be solved with a simple trick of inclusion-exclusion principle.

To calculate coprimes of n less than m, we first calculate numbers less than m which are not coprimes to n and then subtract it from m.

For example, we have to find coprimes of 30 less than 20.
Now prime factors of 30 are 2,3,5. To find non-coprime numbers of 30 less than 20, we find number of multiples of 2,3 & 5 less than 20.

Number of multiples of 2 = 20/2 = 10
Number of multiples of 3 = 20/3 = 6
Number of multiples of 5 = 20/5 = 4

Total multiples = 10+6+4 =20

But, here some multiples of 2 & 3 are repeated.
Number of repeated multiples of 2 & 3 = 20/(2*3) = 20/6 = 3

Similarly,
Number of repeated multiples of 2 & 5 = 20/(2*5) = 20/10 =2
Number of repeated multiples of 3 & 5 = 20/(3*5) = 20/15 = 1

Now, extra deleted multiples are
Number of repeated multiples of 2,3&5 = 20/(2*3*5) = 20/30 =0

So, number of multiples of 2,3,5 less than 20= 10+6+4-3-2-1+0 = 14

Hence, number of non-coprimes of 30 less than 20 = 14

and number of coprimes of 30 less than 20 = 20-14 = 6
(which are 1, 7, 11, 13, 17 and 19)

This method is application of inclusion-exclusion principle. It can be implemented in code using recursive funcion.

Following code can be used for finding above:

#include<stdio.h>
#include<math.h>
 
/*Start of code for  storing prime numbers upto 100000 (sieve using byte array)*/
 
int *Prime[100000>>5];
int pos[9594];                                      //stores prime numbers
#define prime(i) ((Prime[i>>5])&(1<<(i&(31))))
#define set(j) (Prime[j>>5]|=(1<<(j&(31))))
#define LIM 100000
#define SLIM 317

int sieve()
{
        int i, j, m, n, t,x,k,l,h;
        set(1);
        pos[1]=2;
        pos[2]=3;
        for(k=2,l=3,i=5; i<=SLIM; k++,i=3*k-(k&1)-1)
                if(prime(k)==0)
                {
                        pos[l++]=i;
                        for(j=i*i,h=((j+2)/3); j<=LIM; h+=(k&1)?(h&1?((k<<2)-3):((k<<1)-1)):(h&1?((k<<1)-1):((k<<2)-1)),j=3*h-(h&1)-1);
                        set(h);
                }

        i=3*k-(k&1)-1;

        for(; i<=LIM; k++,i=3*k-(k&1)-1)
        if(prime(k)==0)
        {pos[l++] = i;isPrime[i]=true;}

        return l;
}
//End of code for prime numbers 
 
int coprimes(int *factors,int start,int nf,int m) //calcualates  multiples less than m
{

    int sum=0;

    if(start==nf-1) return (m/factors[start]);

    return

      (m/factors[start]+coprimes(factors,(start+1),nf,m) - coprimes(factors,(start+1),nf,m/factors[start]));

}

int main() { 
 
        int x=sieve();
        int n,m;

        scanf("%d %d",&n,&m);
        int i,nf=0;         //nf is number of prime factors

        int factors[17];   //stores prime factors of n
 
        for(i=1;pos[i]<=m;i++)
        {
            if(n%pos[i]==0) {factors[nf++]=pos[i];}
        }

        if(nf==0) printf("%d\n\n",m);
 
        else
       {
        int lim=coprimes(factors,0,nf,m);
        printf("%d\n\n",m-lim);
       }
    }
         return 0;
}

Here, first we find all prime numbers upto 100000 so that it is easy to calculate prime factors of number. For this, I used sieve of erathronese using byte array. Also, multiples of 2 and 3 are skipped in the sieve to increase time complexity.
Prime factors are stored in array factors.
Then recursive function coprimes is called and finally answer is printed.

Sieve of Erathronese using Byte Array

(bit manipulation)

 Sieve of erathronese is a easy marking technique for finding prime numbers in less time.Using byte array for checking and marking of prime numbers increases space complexity as well as time complexity (as bit manipulations are fast). Using byte array 1 integer can be used to store 32 numbers.

Following code prints prime numbers upto 32000:

#include <iostream>
 
int arr[10000];
#define set(i) (arr[i>>5]|=(1<<(i&31)))
#define is_compound(i) (arr[i>>5]&(1<<(i&31)))

using namespace std;

int main()
{
    for(int i=3;i<32000;i+=2)
    {
        if(!is_compound(i))
        {
            int k=2*i;
            for(int j=i*i;j<32000;j+=k) set(j);
        }
    }

    cout<<2<<" ";
    for(int i=3;i<32000;i+=2) if(!is_compound(i)) cout<<i<<" ";
    cout<<endl;
}

Code is pretty straightforward. We have skipped even numbers for increasing time complexity.

This is my first post which I am writing almost after the year I created my blog.

Today, it is the last day of my vacation after first year.First year was really the successful year in my life and probably in the engineering career ,as I stood first in the VJTI college.I never thought that I could achieve this ,but fortunately it happened.This had brought a positive attitude to me for my remaining three years of engineering.