• About

j.matthew.turner

~ Director. Videographer. Editor. Geek.

Monthly Archives: October 2014

Project Euler #5: Smallest Multiple

29 Wednesday Oct 2014

Posted by jmatthewturner in C++, Geekery, Programming, Project Euler, Python

≈ Leave a comment

Tags

c++, programming, projecteuler, python, smallestmultiple

From ProjectEuler.org:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Image of C++ CodePretty straightforward: a nested loop that checks for divisibility inside another loop that counts up by 20 until the answer is found. Just a couple things I’ll say about this:

  • In constructing the inner loop, I counted down from 20 (instead of up from 1) because I figure fewer numbers are divisible by 20 and 19 than by 1 and 2. This way the first false condition is found sooner than later, and no time is wasted.
  • Further, every integer from 1 to 10 divides evenly into some integer from 11 to 20. Therefore it’s not necessary to check 1-10; 11-20 is enough.
  • I constructed my loop using a boolean flag, isDivisble, that is reset every time we increase the outer loop by 20. The flag allows me to break out of the inner loop as soon as I find a number that is not divisible, so no time is wasted.
  • Although my compiler allows me to use an int and still come up with the correct answer, the C++ standard only requires an int to hold 16 bits, or ~65,000 unique values (positive and negative). Since the answer is greater than 65,000/2, an int on some compilers may not produce the correct answer. A long is guaranteed to hold at least 32 bits, or over 4 billion unique values, so I used a long in my solution just as a best practice. With only that change, it takes twice as long to run. Efficiency is priority #1, people!
Project Euler #5 Solution

Project Euler #5 C++ Solution

C++ Code:

#include <iostream>

using namespace std;

bool isDivisible;

int main()
{
    for (long i = 2520; ; i += 20){
        isDivisible = true;
        for (int j = 20; j > 10; j--){
            if (!(i%j == 0)){isDivisible = false; break;}
        }
        if (isDivisible){cout << endl << "The smallest number evenly divisible by all integers between 1 and 20 is: " << i << "." << endl << endl; break;}
    }
    return 0;
}

Python won’t allow an indefinite range in a for loop, so I had to rewrite it to use a while loop. Same basic structure, though:

i = 2520

while True:
    isDivisible = True;
    for j in range(20, 10, -1):
        if i%j is not 0:
            isDivisible = False
            break
    if isDivisible:
        print ""
        print "The smallest number that is evenly divisible by all integers between 1 and 20 is " + str(i) + "."
        break
    else:
        i += 20

Use NeoFinder to Reclaim Hard Drive Space

28 Tuesday Oct 2014

Posted by jmatthewturner in Editing, Mac, Organization, Yosemite

≈ Leave a comment

Tags

backup, editing, freelance, osx

NeoFinder

Duplicates Found

I’ve written about NeoFinder before. It’s a great tool to keep tabs on files across multiple external hard drives. (Basically, it creates a searchable database of every file on each of your drives, which you can then quickly search even when those drives are not plugged in.)

Ok, so that’s great. Easily worth the cost of a license. But what’s even better is the built-in “Find Dupes” feature. Once you’ve cataloged all your drives, just hit the Find Dupes button and it will let you know what projects or files are living on multiple drives.

I cleared over 100 GB in just a couple minutes when it reminded me that I had started a recent project on one drive and then moved it to a portable drive to finish it. (And it found quite a bit more than that, which I’ll deal with when I have a bit more time.)

Check out NeoFinder if you haven’t already. Really – I’m totally vouching over here. Great stuff.

OS X Yosemite Uploads Local Data to Apple without Users’ Consent (Or Does It?)

28 Tuesday Oct 2014

Posted by jmatthewturner in Yosemite

≈ Leave a comment

Tags

Apple, geekery, osx, privacy, yosemite

OS X Yosemite

OS X Yosemite

Security guru Bruce Schneier points out an article detailing a new “feature” of Yosemite, wherein as-yet-unsaved text files and email addresses are uploaded to Apple’s servers without users’ knowledge or consent. Check out his summary here, and click through for the full explanation. Commenters point out that this is disclosed in Apple’s knowledgebase (and I’m sure it’s buried in a TOS somewhere, so “without users’ consent” may be technically inaccurate), and that – essentially – it should be expected behavior for iCloud users. It is an interesting world we live in where the is a legitimate debate over “OMG! I just discovered my personal computer is uploading my private data to a corporate server without my knowledge!!” vs “of course it is, doofus. Didn’t you assume it was? It makes life easier!” I feel a little weird about it, but I think I come down on the latter side. If you have an iCloud account (I’m assuming this only applies to people with iCloud accounts, though I don’t know for sure), then you should assume that your unsaved documents are going there, too, because it DOES make life easier. iCloud gonna iCloud.

Setting up Boost C++ Libraries for Large Integers in Code::Blocks on OS X

21 Tuesday Oct 2014

Posted by jmatthewturner in C++, Geekery, Mac, Programming

≈ 1 Comment

Tags

BigInts, boost, c++, code::blocks, mac, programming, projecteuler

Having trouble getting integers larger than 64 bits to work in C++? So was I. Here’s how I fixed it:

  1. You’ll want to use the data type cpp_int provided by Boost C++ Libraries.
    1. Go here and download the zip: http://sourceforge.net/projects/boost/files/boost/1.56.0/
    2. Unzip into a forever home. (You’ll probably want this again sometime, so don’t just stick it in your project folder and forget about it.)
  2. Code::BlocksCode::Blocks needs some priming before you can use Boost:
    1. With your project open, choose: Project->Build Options….
    2. Select the Search Directories tab.
    3. Use the Add button at the bottom to add the path to your new Boost directory. This needs to be the directory that was created when you extracted the zip file. (In my case, I added /Users/jmatthewturner/C++/Boost/boost_1_56_0.)
  3. And your project file needs some special code:
    1. Add an #include for the cpp_int.hpp file that is inside boost/multiprecision/. Mine looks like this:
      #include "/Users/jmatthewturner/C++/Boost/boost_1_56_0/boost/multiprecision/cpp_int.hpp"

Now you can use the data type cpp_int, which is an arbitrarily large integer, limited only by the memory available on your machine. It is part of the namespace boost::multiprecision, so always refer to it like this:

boost::multiprecision::cpp_int myBigInteger;

or define a namespace to make your life a little easier:

using namespace std;
namespace mp = boost::multiprecision;
mp::cpp_int myBigInteger;
mp::cpp_int myFunction(mp::cpp_int x);

…etc, etc. And that should do it. I used cpp_int to help solve Project Euler #20; I’ll post the source code when I get around to writing up the problem.

OS X Yosemite and Adobe Creative Cloud 2014

19 Sunday Oct 2014

Posted by jmatthewturner in Creative Cloud, Editing, Geekery, Mac, Premiere Pro

≈ Leave a comment

Tags

adobe, Adobe Creative Cloud, adobe premiere pro cc, Apple, creative cloud, Creative Cloud applications, osx, yosemite

When Adobe released its 2014 Creative Cloud applications earlier this year, I put off upgrading due to the usual concerns of “I am not your guinea pig.” But with Apple’s release of Yosemite this week, I decided it was time.

OS X Yosemite

OS X Yosemite

I installed Yosemite this morning, and promptly spent an hour on Apple Maps doing 3D flyovers of various cities. (I gather this feature has been available on Mavericks for a while, but since I never use Apple Maps, I only found it when it got added back to my dock.)

After that I had to download and install an update to TotalFinder (my older version was broken on Yosemite, and I simply cannot be without it for a moment). Although the update is listed as beta, it seems fine so far.

I’ll spare you the laundry list of changes (if laundry lists are your thing, check out Apple’s product page and Lifehacker’s Top Ten Hidden Features), but I do like the changes to Spotlight, and why on Earth it took them this long to make the Full Screen button actually make an app go full screen, I’ll never understand.

Adobe Creative Cloud 2014

Adobe Premiere Pro 2014Next I installed Premiere Pro 2014, and opened up a recent project to putz around. I immediately had to download new versions of and reinstall my plugins (and in one case buy an upgrade) to get everything to work properly. But once that was done, smooth sailing.

Of course the previous version of Premiere sits alongside 2014, so I was able to go back into my old project when I needed to gather some details to recreate one of those upgraded plugin effects.

All told, it has so far been relatively painless. I did have one crash the first time I opened Premiere, but I’ve closed and reopened it many times since then and it hasn’t repeated. (I suspect it was related to one of the outdated plugins sitting in the timeline.) Editing the project to recreate the various plugin effects exposed no problems, and an export through Media Encoder 2014 worked perfectly.

In sum, this Late 2013 iMac seems to be running both Yosemite and Premiere 2014 without a hitch. I’ll install the rest of CC 2014 in the coming days and update this post; I’ll do the same upgrades on my Mid 2009 MBP soon and post those results separately.

Project Euler #4: Palindromic Numbers

12 Sunday Oct 2014

Posted by jmatthewturner in C++, Geekery, Programming, Project Euler, Python

≈ Leave a comment

Tags

c++, programming, python

Project Euler #4 finds the largest palindrome that is the sum of two 3-digit numbers:

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

My solution uses 3 chunks of code:

  1. a nested for loop that finds products of all 3-digit factor pairs
  2. a function that converts a product into a string
  3. a function that determines if a string is a palindrome

As usual, I wrote the solution in C++ first, but this is really the first Project Euler problem that may have been easier in Python. It certainly is easier to read in Python – the language’s string syntax is much more straightforward than C++. The solutions are functionally identical, but I think the isPalindrome() code in Python is really much more readable.

Here it is in C++:

#include <iostream>
#include <string>

using namespace std;

// the function isPalindrome returns true if a given string is a palindrome
bool isPalindrome(string x){
    if (x.length() == 1){return true;}
    if (x.length() == 2){if (x[0] == x[1]) {return true;} return false;}
    if (x[0] == x[x.length()-1]){return isPalindrome(x.substr(1,x.length()-2));}
    return false;
}

// the function isPalindromeHelper converts an int into a string
// and returns the result of isPalindrome(<string>)
bool isPalindromeHelper(int x){
    string numString = to_string(x);
    return isPalindrome(numString);
}

int main()
{
    int highestPalindrome = 0;
    int highesti = 0;
    int highestj = 0;
    for (int i = 999; i > 99; i--){
        for (int j = 999; j > 99; j--){
            if (isPalindromeHelper(i*j)){
                if (highestPalindrome < i*j){highestPalindrome=i*j; highesti=i; highestj=j;}
            }
        }
    }
    cout << endl << "The largest palindrome that is the product of two 3-digit numbers is: " << highestPalindrome << " (" << highesti << " x " << highestj << ")." << endl;
    return 0;
}

And in Python:

def isPalindrome(x):
    if (len(x) is 1): return True
    if (len(x) is 2): 
        if (x[0] is x[1]): return True
        else: return False
    if (x[0] is x[-1]): return isPalindrome(x[1:-1])

def isPalindromeHelper(x):
    numString = str(x)
    return isPalindrome(numString)
    
highestPalindrome = 0
highesti = 0
highestj = 0
for i in range(100, 1000, 1):
    for j in range(100, 1000, 1):
        temp = i*j
        if isPalindromeHelper(temp):
            if (temp > highestPalindrome):
                highestPalindrome = temp
                highesti = i
                highestj = j
print ""
print "The largest palindrome that is the product of two 3-digit numbers is " + str(highestPalindrome) + " (" + str(highesti) + "x" + str(highestj) + ")."
C++ Output

C++ Output

Adobe Premiere Pro / Audition Roundtrip Tutorial

09 Thursday Oct 2014

Posted by jmatthewturner in Creative Cloud, Editing, Premiere Pro

≈ Leave a comment

Tags

adobe, adobe premiere pro cc, audio, audition, creative cloud, editing

I created this tutorial for anyone who needs an overview of working with audio in Adobe Premiere Pro and Audition. It includes a basic roundtrip, splitting a stereo track into mono tracks, normalizing speech with the Speech Volume Leveler, and EQ’ing for voice.

Adobe Doesn’t Care about Android People

06 Monday Oct 2014

Posted by jmatthewturner in Creative Cloud

≈ Leave a comment

Tags

adobe, adobe premiere pro cc, android, editing, lightroom mobile, photoshop mix, premiere clip

Adobe Premiere Clip

Andrwhat?

Adobe just announced the release of mobile versions of its Creative Cloud apps for media creation. Which is great, except that for Adobe, “mobile” apparently means “iPhone.”

At least for any of the apps that matter. A few are available for Android, but not Premiere Clip, not Lightroom Mobile, and not Photoshop Mix.

Creative Cloud / Mobile Apps

So, Adobe: a little help?

Project Euler #3: Largest Prime Factor

05 Sunday Oct 2014

Posted by jmatthewturner in C++, Geekery, Programming, Project Euler, Python

≈ 1 Comment

Tags

c++, programming, projecteuler, python

Project Euler #3 looks for the largest prime factor of 400 billion and something. It is a straightforward problem, but it can be a study in efficiency. The trouble is that the given number is so large that the usual brute force method of counting up from 1 and checking every number would take WAY too long. Like it would still be running, and I wrote it weeks ago. Here’s the problem, as posited by projecteuler.net:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

My first thought was to simply start at 3, count up by 2’s (thus eliminating wasted time spent testing even numbers, which obviously aren’t prime), and test every odd number to see if it is a) prime, and b) a factor of 400 billion whatever. This method actually finds the answer very quickly, but it doesn’t KNOW it has found the correct answer until it tests a bajillion more numbers to prove that they AREN’T prime factors.

So I had to rethink my strategy. And what I came up with was to work backward, using reciprocals. Like this:

  1. Start a loop as described above, starting at 3 and counting up by 2’s (a note on where you need to count up to in a moment).
  2. On each loop iteration, check the current (odd) number ONLY to see if it’s a factor of 600 bizizzle. If it isn’t, move on.
  3. If it is, then we have actually found a really LARGE factor, in the reciprocal. i.e., 600,851,475,143 / 71 = 8,462,696,833. So, by counting up from 3, we quickly find that 71 is a factor; but we also have found that 8,462,696,833 is a factor, too. And not just any factor, but the largest factor.
  4. Next, check that reciprocal to see if it happens to be prime. If not, keep going.
  5. If it is, then stop and deliver the answer. Because with this method, the very first prime that we come across will necessarily be the largest prime factor.

In other words, this algorithm identifies factors of 600 billionzy, in decreasing order, starting with the largest. My implementation printed them as it went, so the output (spoiler alert) looks like this:

Screenshot 2014-10-02 14.55.13

Project Euler #3: Largest Prime Factor (~1s method)

Thing is, this still isn’t the most efficient method. Because in my zeal for working backwards, I completely discarded the smaller factors that I found. (i.e., I tested 8,462,696,833, but ignored 71.)

The unconscious assumption was that the largest prime factor would be among the largest 50% of all factors. But it isn’t.

Another rewrite follows the same algorithm as above, except instead of only looking at the large factors and assuming the first prime it finds will be the largest, it tests the smaller factors on the way up, as well, and keeps track of the largest prime it has found at all times. So when it finds 71, and determines its reciprocal of 8,462,696,833, it tests both for primality before moving on to the next pair.

Project Euler #3: Largest Prime Factor (0.007s method)

Project Euler #3: Largest Prime Factor (0.007s method)

That change took the execution time from ~1 second to 0.007 seconds.

Now, regarding the loop controls. A big question I had when I started was “how far up do I have to count before I know I’ve found all the factors?” Because 400 billion is big. And I had essentially the same question for the boolean function isPrime() (which checks for primality): “how far up do I have to count before I know the number is prime?”

At first, I had isPrime(x) testing every number up to x/2 looking for factors. (ie, if I called isPrime(17), my original implementation tried to divide {1, 2, 3, … 8} into 17 before it gave up and determined that 17 is prime.

But what I figured out was that you only need to check up to the square root of the number – again, because of reciprocals.

For example, 100 is divisible by 2, 4, 5, 10, 20, 25 and 50. Notice anything? Look at those same numbers like this:

{2,     4,     5,    10}
{50,   25,    20,    10}

If I Divide 100 by 2, I get 50. So I know that it’s divisible not just by 2, but by BOTH of those numbers. Similarly, testing 4 yields both 4 and 25 as factors, testing 5 yields both 5 and 20 as factors, and testing 10 reveals 10 as the square root. In terms of our isPrime() algorithm, what that means is that once I test a given number up to its square root, I have effectively tested everything after the square root, as well. Because reciprocals. Make sense?

In any case, that applies to the main function, as well – once you’ve reached the square root, you’ve identified all the factors.

So I started with a perfectly correct solution that would have taken just over 13 days to complete (really – I checked), then found another that takes just under 1 second, and finally arrived at one that takes 0.007 seconds. All valid solutions, but what a difference in efficiency.

Here’s the final code in C++:

#include <iostream>
#include <math.h>

using namespace std;

bool isPrime(long long x){
    if ((x == 2) || (x == 3)){return true;}
    if ((x == 1) || (x%2 == 0)) {return false;}
    for (long long i = 3; i <= sqrt(x); i+=2){
        if (x%i == 0){return false;}
    }
    return true;
}

int main()
{
    long long number = 600851475143;
    long long largestFactor = 1;

    for (long long i = 3; i < sqrt(number); i+=2){
        if (number%i == 0){
            cout << endl << "Factor: " << i;
            if (isPrime(i)){
                cout << " ---------- Prime";
                if (i > largestFactor) {largestFactor = i;}
            }
            cout << endl << "Factor: " << number/i;
            if (isPrime(number/i)){
                cout << " ---------- Prime";
                if (number/i > largestFactor) {largestFactor = number/i;}
            }
        }
    }

    cout << endl << endl << "The largest prime factor of 600,851,475,143 is " << largestFactor << "." << endl << endl;
    return 0;
}

And here it is in Python:

import math

def isPrime(x):
   if (x is 2) or (x is 3):
       return True
   if (x is 1) or (x%2 is 0):
       return False
   for i in range(3,int(math.sqrt(x)+1),2):
       if (x%i is 0):
           return False
   return True

number = 600851475143
largestFactor = 1

for i in range(3,int(math.sqrt(number)),2):
    if (number%i is 0):
        print "Factor: " + str(i)
        if isPrime(i):
            print "        ^^^^ Prime"
            if (i > largestFactor):
                largestFactor = i
        print "Factor: " + str(number/i)
        if (isPrime(number/i)):
            largestFactor = number/i
            print "        ^^^^ Prime"
            
print "The largest prime factor of 600,851,475,143 is " + str(largestFactor) + "."

Link

A Brief Look at Texting and the Internet in Film

03 Friday Oct 2014

Posted by jmatthewturner in Editing, Film

≈ Leave a comment

Tags

editing, film, movies

A Brief Look at Texting and the Internet in Film

A Brief Look at Texting and the Internet in Film

Didn’t mean to post two of these in a row, but this guy’s videos are pretty great. This one is about the evolving visual representation of the internet/technology in film.

I first noticed the on-screen texting thing earlier this year in Chef (2014). I guess I need to get out more.

← Older posts

Recent Posts

  • Premiere Pro’s Project Manager Can’t Handle Double-Nests
  • Encrypt Your Dropbox Files with VeraCrypt
  • Mortal Kombat and Enter the Dragon Are the Same Movie
  • 16×9 Linux VMs Inside VirtualBox
  • Adobe Releases Creative Cloud 2015

Categories

  • Advertising
  • Apple
  • C++
  • Creative Cloud
  • Editing
  • Film
  • Geekery
  • Linux
  • Mac
  • Marketing
  • Organization
  • Panasonic
  • Premiere Pro
  • Programming
  • Project Euler
  • Python
  • SEO
  • Shooting
  • Uncategorized
  • Yosemite

Recent Comments

Miquel Parejo on Premiere Pro’s Project M…
Meny on Premiere Pro’s Project M…
dnn on Project Euler #6: Sum Square…
jmatthewturner on Premiere Pro Audio Synching Pi…
Kalyan on Premiere Pro Audio Synching Pi…

Archives

  • June 2017
  • July 2016
  • July 2015
  • June 2015
  • April 2015
  • February 2015
  • January 2015
  • December 2014
  • November 2014
  • October 2014
  • September 2014
  • May 2014
  • September 2013

Meta

  • Register
  • Log in
  • Entries feed
  • Comments feed
  • WordPress.com

Create a free website or blog at WordPress.com.

Cancel
Privacy & Cookies: This site uses cookies. By continuing to use this website, you agree to their use.
To find out more, including how to control cookies, see here: Cookie Policy