Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[SethCreiyd]

Hey Mego, thanks for the link to Project Euler, which is duly awesome.  Thanks to that I've finally realized how much this:

Code: [Select]

if (n % x == 0) and is_prime_number(x): pfactor = x
# time: <1 sec
is better than this:

Code: [Select]

if is_prime_number(x) and (n % x == 0): pfactor = x
# time: >5 sec

[Skyrunner]

My school is offering an Information Tech class, which is computer app plus C++.

...Should I take it, or should I just go with a foreign language? I have a feeling it'll be just dabbling in programming.


Project Euler is too hard for me maths wise; I can't understand most of the problems there :c
Also, I don't see what's the difference between those two :-0

[Siquo]

A bit of computer takes you further than a bit of foreign, career/utility wise.

[Skyrunner]

But (I think) I already know what they're going to teach. All of it. :<

Also, I don't believe in Korean public high schools' ability to teach both foreign languages and inf tech. :C

[SethCreiyd]

Also, I don't see what's the difference between those two :-0

Neither did I beforehand, not really.  The problem was to find the largest prime factor of n:

Spoiler (click to show/hide)

Code: [Select]

def largest_pf(n):
    pf = None
    for x in xrange(1, int(n**0.5)+1, +2):
        if (n % x == 0) and is_prime(x): pf = x
    return pf
where is_prime is:

Code: [Select]

def is_prime(x):
    x = abs(int(x))
    if x < 2: return False
    if x == 2: return True
    if x % 2 != 1:  return False   # even numbers >2 can't be primes

    for i in range(3, int(x**0.5)+1, +2):
        if x % i == 0: return False    # if x / i leaves no remainder

    return True
The problem gives n as a 12 digit integer, and is_prime(x) gets very expensive.  (n % x == 0) takes much less time to compute for large values than is_prime(x) does, so it should be executed first.  No need to see if x is a prime number if it can't be a prime factor.

Probably old-hat to experienced coders, but despite seeming an important aspect of coding it's not something I really understood until having to deal with the difference. 

[Skyrunner]

Oh, for and, if the first thing is wrong, the second is skipped?

Something new every day. o_O


...Does this work in C++ too? In which if( is_prime() && n%x == 0) is slower than if( n%x == 0) && is_prime()?

[Thief^]

Hey Mego, thanks for the link to Project Euler, which is duly awesome.  Thanks to that I've finally realized how much this:

Code: [Select]

if (n % x == 0) and is_prime_number(x): pfactor = x
# time: <1 sec
is better than this:

Code: [Select]

if is_prime_number(x) and (n % x == 0): pfactor = x
# time: >5 sec

Project Euler is too hard for me maths wise; I can't understand most of the problems there :c
Also, I don't see what's the difference between those two :-0

Most computer languages short-circuit "and" tests: they skip evaluating the right-hand-side completely if the left-hand-side is false. In this case, because the speed of the two sides is different, you can get a significant speed boost by putting the fast test (the (n % x == 0)) on the left, and putting the slow test (the is_prime_number(x)) on the right, where it will get skipped a lot of the time.

The skipping is often used with validity testing (e.g. c++ code):
if (pX != nullptr && pX->Y > 0)
...will only try to access Y in pX if pX is not null. This is important because trying to access anything via a null pointer will crash the program.

[Thief^]

"or" tests also short-circuit, but the opposite way: The right isn't evaluated if the left is *true*.

For the exact opposite of the test above:
if (pX == nullptr || pX->Y <= 0)
Will again not try to access pX->Y if pX is null, this time resulting in a true if instead of a false one.

[Siquo]

So, in short, you put the fastest test on the left side, with both "and" and "or". Also, if the tests are more or less the same, but you expect one to fail a lot more than the other, putting that one in front helps (in case of an and) or on the right (in case of an or).

So, for instance:

Code: [Select]

for x = -1 to 1000 {
  if (x < 10 && x > 0)
}is faster than

Code: [Select]

  if (x > 0 && x < 10)

[Thief^]

Actually I just tried it using GCC Explorer and they both optimise to the same assembly.
Confusing assembly that I can't find the > 0 test in at all.

Code: [Select]

#include <iostream>

int main()
{
  int y;
  for (int x = -1; x < 1000; x++)
  {
    if (x > 0 && x < 10)
    {
      y = x;
    }
  }
 
  std::cout << y;
 
  return 0;
}


Code: [Select]

main:
mov eax, -1 // x = -1
.L3:
lea edx, [rax-1] // edx = x - 1
cmp edx, 8 // compare edx to 8
cmovbe esi, eax // if (edx <= 8) y = x
add eax, 1 // x++
cmp eax, 1000 // compare x to 1000
jne .L3 // jump to L3 (loop start) if x != 1000
sub rsp, 8 // from here on deals with the cout call
mov edi, OFFSET FLAT:std::cout
call std::basic_ostream<char, std::char_traits<char> >::operator<<(int)
xor eax, eax
add rsp, 8
ret
sub rsp, 8
mov edi, OFFSET FLAT:std::__ioinit
call std::ios_base::Init::Init()
mov edx, OFFSET FLAT:__dso_handle
mov esi, OFFSET FLAT:std::__ioinit
mov edi, OFFSET FLAT:std::ios_base::Init::~Init()
add rsp, 8
jmp __cxa_atexit

(note it still loops 1000 times even though there's no result from doing so apart from wasting time. Make sure you break loops as early as possible!)

EDIT: Figured it and it's really fecking clever. cmovbe is a conditional move based on an *unsigned* below-or-equal comparison. When x-1 is negative, it'll interpret it as a very large number, and therefore > 8 (>=10 in the original code). The signed version is cmovle (conditional-move-on-less-or-equal). Yes that's confusing.

[Mego]

Actually I just tried it using GCC Explorer and they both optimise to the same assembly.
Confusing assembly that I can't find the > 0 test in at all.

Code: [Select]

#include <iostream>

int main()
{
  int y;
  for (int x = -1; x < 1000; x++)
  {
    if (x > 0 && x < 10)
    {
      y = x;
    }
  }
 
  std::cout << y;
 
  return 0;
}


Code: [Select]

main:
mov eax, -1 // x = -1
.L3:
lea edx, [rax-1] // edx = x - 1
cmp edx, 8 // compare edx to 8
cmovbe esi, eax // if (edx <= 8) y = x
add eax, 1 // x++
cmp eax, 1000 // compare x to 1000
jne .L3 // jump to L3 (loop start) if x != 1000
sub rsp, 8 // from here on deals with the cout call
mov edi, OFFSET FLAT:std::cout
call std::basic_ostream<char, std::char_traits<char> >::operator<<(int)
xor eax, eax
add rsp, 8
ret
sub rsp, 8
mov edi, OFFSET FLAT:std::__ioinit
call std::ios_base::Init::Init()
mov edx, OFFSET FLAT:__dso_handle
mov esi, OFFSET FLAT:std::__ioinit
mov edi, OFFSET FLAT:std::ios_base::Init::~Init()
add rsp, 8
jmp __cxa_atexit

(note it still loops 1000 times even though there's no result from doing so apart from wasting time. Make sure you break loops as early as possible!)

EDIT: Figured it and it's really fecking clever. cmovbe is a conditional move based on an *unsigned* below-or-equal comparison. When x-1 is negative, it'll interpret it as a very large number, and therefore > 8 (>=10 in the original code). The signed version is cmovle (conditional-move-on-less-or-equal). Yes that's confusing.

Different compilers (and even compiler versions!) will optimize differently, especially if you're using optimization flags. Because of that, it's best to write code in the most optimized form you can. Don't take a smart compiler for granted.

[MagmaMcFry]

Also, I don't see what's the difference between those two :-0

Neither did I beforehand, not really.  The problem was to find the largest prime factor of n:

Spoiler (click to show/hide)

Code: [Select]

def largest_pf(n):
    pf = None
    for x in xrange(1, int(n**0.5)+1, +2):
        if (n % x == 0) and is_prime(x): pf = x
    return pf
where is_prime is:

Code: [Select]

def is_prime(x):
    x = abs(int(x))
    if x < 2: return False
    if x == 2: return True
    if x % 2 != 1:  return False   # even numbers >2 can't be primes

    for i in range(3, int(x**0.5)+1, +2):
        if x % i == 0: return False    # if x / i leaves no remainder

    return True
The problem gives n as a 12 digit integer, and is_prime(x) gets very expensive.  (n % x == 0) takes much less time to compute for large values than is_prime(x) does, so it should be executed first.  No need to see if x is a prime number if it can't be a prime factor.

Probably old-hat to experienced coders, but despite seeming an important aspect of coding it's not something I really understood until having to deal with the difference. 

Here's a much faster algorithm:

Spoiler (click to show/hide)

Code: [Select]

int largest_prime_factor(int n) {
  int p = 2;
  while (p * p <= n) {
    n % p == 0 ? n /= p : ++p;
  }
  return n;
}


[Thief^]

Different compilers (and even compiler versions!) will optimize differently, especially if you're using optimization flags. Because of that, it's best to write code in the most optimized form you can. Don't take a smart compiler for granted.

Oh of course, but you also shouldn't try to optimise something until you've proven that there's a problem with it (and afterwards, can prove that you helped). Optimisation's not as easy as it sounds.

[Mego]

Different compilers (and even compiler versions!) will optimize differently, especially if you're using optimization flags. Because of that, it's best to write code in the most optimized form you can. Don't take a smart compiler for granted.

Oh of course, but you also shouldn't try to optimise something until you've proven that there's a problem with it (and afterwards, can prove that you helped). Optimisation's not as easy as it sounds.

Yes, I'm aware of this. Working product before shiny product.

On another note, Java is baffling me.

Spoiler: GameButton.java (click to show/hide)

Code: [Select]

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import java.io.*;

public class GameButton extends JButton {
    GameGUI gameg;
    GamePieces color;
   
    public GameButton(String imgFile, GameGUI gguiInstance) throws IOException {
        super(new ImageIcon(imgFile));
        gameg = gguiInstance;
        if(imgFile.equals("black.png")) color = GamePieces.BLACK;
        else if(imgFile.equals("white.png")) color = GamePieces.WHITE;
        else color = GamePieces.EMPTY;
    }
   
    public void mouseClicked(MouseEvent e) {
        if(e.getButton() == MouseEvent.BUTTON1) gameg.processClick(this);
        System.out.println("GameButton " + this.toString() + " pressed.");
    }
   
    public int getXPos() {
        return (int)super.getX()/100;
    }
   
    public int getYPos() {
        return (int)super.getY()/100;
    }
   
    public GamePieces getColor() {
        return this.color;
    }
}


Spoiler: GameGUI.java (click to show/hide)

Code: [Select]

import javax.swing.*;
import java.awt.*;
import java.io.*;

public class GameGUI {
    JFrame frame;
   
    public GameGUI(JFrame frame) {
        this.frame = frame;
    }
   
    public void processClick(GameButton gb) {
        String fileName;
        if(gb.getColor() == GamePieces.BLACK || gb.getColor() == GamePieces.EMPTY) fileName = "white.png";
        else fileName = "black.png";
        frame.remove(gb);
        try {
            gb = new GameButton(fileName, this);
        } catch(IOException e) {
            return;
        }
        frame.getContentPane().add(gb);
        frame.pack();
        frame.setVisible(true);
    }
   
}


Spoiler: GamePieces.java (click to show/hide)

Code: [Select]

public enum GamePieces
{
    EMPTY, BLACK, WHITE;
}


Spoiler: GUITest.java (click to show/hide)

Code: [Select]

import java.io.IOException;
import javax.swing.*;
import java.awt.*;

public class GUITest {
    public static void main(String[] args) throws IOException {
        JFrame testFrame = new JFrame("Game Window (debug)");
        GameGUI gg = new GameGUI(testFrame);
       
        testFrame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        testFrame.getContentPane().add(new GameButton("black.png", gg));
        testFrame.pack();
        testFrame.setVisible(true);
    }
}


Everything appears to work fine. The window appears with a button in it, which has the icon represented by black.png. Except, when I try to click it, nothing happens. The various debugging things I put in GameButton.mouseClicked and GameGUI.processClick aren't doing anything. Where am I going wrong?

[SethCreiyd]

Here's a much faster algorithm:

Spoiler (click to show/hide)

Code: [Select]

int largest_prime_factor(int n) {
  int p = 2;
  while (p * p <= n) {
    n % p == 0 ? n /= p : ++p;
  }
  return n;
}


Indeed it is, thanks.  Not just faster either:

Spoiler (click to show/hide)

Code: [Select]

@timed
def lpf1(n):
    pf = None
    for x in xrange(1, int(n**0.5)+1, +2):
        if (n % x == 0) and is_prime(x): pf = x
    return pf

>>> @timed
def lpf2(n):  # had to modify a bit to accommodate Python
p = 2
while (p * p <= n):
if n % p == 0: n /= p
else: p += 1
return n

>>> lpf1(546786256789)
lpf1 took 131.000 ms
823
>>> lpf2(546786256789)
lpf2 took 16.000 ms
664381843L

>>> lpf1(n) == n/lpf2(n)
True

# huh?

I'm not sure what's exactly wrong with lpf1, but I think it's the square root / conversion to int in the for loop.  lpf1(n) is returning the quotient of n / lpf2(n).
At any rate, my version stinks.  ^_^