뭘 이런걸..

Filed under Tech/프로그래밍
출처: http://forums.parallax.com/showthread.php?114807-Fast-Faster-Fastest-Code-Integer-division

page 없어질 까봐 스크랩 함.

Hi All,

A code or algorithm must be correct. When it is, after some debugging, we can make a compromise between its code size and speed. There is always a compromise, but sometimes it does not matter. When either speed or size is a factor, there are methods to boost performance. There might be a 'Small, Smaller, Smallest' flavor of coding for a given language/hardware combination, but in this kind of thread I am looking for very fast codes. As, we have these days the luxury of more and more code space, but of time, we don't.

Even when divide hardware is available, it is quite common to find that divide instructions take more than twice as long as multiply instructions. When division and multiplication are done by software, dividing is usually slower than multiplying, too. However, we can improve speed by noticing, that many integer division operations found in real programs involves division by a constant. When we know the numbers we are dividing by in advance, we can substitute the divisions with multiplications and with some bit shifts.

When the constant to divide by is a power of two, we can shift the number to be divided to the right by the exponent, and that will complete division

(some_integer/constant(=2^N)) = some_integer >> N

This bit shift is only one operation, four ticks with the Propeller. Can we do something similar when the constant is not a power of two? Yes. The·basic idea is to approximate the ratio (1/constant) by another rational number (numerator/denominator) with a power of two as the denominator. Instead of dividing, we can then multiply by the numerator, and shift by the exponent in the denominator. In case of 10, for example, the (1/10) ratio can be substituted with· (205/2048). The (some_integer/10) division can be calculated with a multiplication (some_integer*205), then the product is shifted right 11 bits to get the result of the division by 10. In short notation

(some_integer/10) = (some_integer*205) >> 11

To divide with 100, the rational number (41/4096) works nicely

(some_integer/100) = (some_integer*41) >> 12

For 1000 we can realize that it is 8*125. So, if we first shift 'some_integer' to the right by 3, we only need to divide the result by 125. When (1/125) is approximated as (67109/2^23)=(67109/8388608), then the simple formula

(some_integer/1000) = ((some_integer >> 3)*67109) >> 23

works for integers up to almost 400_000 with high accuracy.

To figure out the (numerator/denominator(=2^N)) approximation for an arbitrary (1/constant) factor, first we have to fix the required relative accuracy of the division. When 1% relative accuracy is adequate for the application
- we multiply the constant with 100.
- Then we find the smallest power of two, that is bigger than the product.·For (1/2009), 262144 is that, so the denominator is 2^18.
- Then, we·obtain the numerator by dividing 2^18 by the constant 2009. That gives 130.48. After rounding to the nearest integer, we have··the·rational approximation·of (1/2009) as (130/2^18).·

It goes, in short

(some_integer/2009) = (some_integer*130) >> 18

Or, doing an evident simplification, it is

(some_integer/2009) = (some_integer*65) >> 17

For a ten times better relative accuracy of 0.1%, the formula is

(some_integer/2009) = (some_integer*1044) >> 21

After simplification, it is

(some_integer/2009) = (some_integer*261) >> 19

The previous simplications decrease the numerator and are useful, since the (some_integer*numerator) product has to be smaller than 2^32, to avoid overflow with the 32-bit multiplication.· 2009 is an odd number. For even constants we can shift out the power of two factor from their primes, before the division. So, to divide with 2010 at 0.1% accuracy, one can use

(some_integer/2010) = ((some_integer >> 1)*1043) >> 20

The initial right shift for an even constant increases the range of validity of the algorithm at the cost of an additional operation.I wonder wether all these beat unrolled division?

We have just substituted a division by a multiplication, but elimination of multiply instructions is itself desirable. For example, according to the Pentium instruction timings, the base time for a 32-bit integer add or subtract on that processor (discounting operand fetch and other overhead) is 1 clock cycle, and both can sometimes be paired with other instructions for concurrent execution. In contrast, a 32-bit multiply takes 10 cycles and a divide takes 41 cycles, and neither can be paired. Clearly, these instructions should be avoided wherever possible.

In case of multiplication with a constant we may ask, that
- Can we can do faster integer multiplication with a constant with only· bit shifts and additions? (The answer is probably: yes. And remember, numerators were contants...)
- Can the (1/constant) ratio be calculated even faster with only bit shifts and additions?

I think the answer for the 2nd. question answers the 3rd, too.··

Trespassing the Regime of Fixed-point math (or not?)...
Fixed-point representations, in which the point is implicitly placed between any bits of the binary representation of a number, have been used since the dawn of the computer age. In the PC world fixed-point arithmetic has become a lost art among programmers. Since the introduction of the 486 CPU, a fast floating-point processor is an integrated part of the CPU, and therefore there is rarely a need to work with fixed-point numbers anymore. In embedded applications fixed-point arithmetic has still its places, and there is no excuse to use inefficient or imprecise methods with those limited resources. Moving away from integer arithmetic to fixed-point numbers is one step forward to close the gap between the speed of integer math and the ease of use of floating point arithmetic.

When fixed-point numbers are used, all arithmetic operations use integer arithmetic, and this leads to a considerable performance advantage. This comes from that a binary fixed point number is, for all purposes, an integer number. You simply cannot tell the difference by looking at it, and neither can the machine level math functions. For those math functions, the numbers are just integers. That's the beauty of it: you use the same machine level functions you would for integer math, plus a little bit of housekeeping for the point at multiplications and divisions. (John Von Neumann said once, that a competent programmer never needs floating point hardware because he should always be able to keep the point in his head. Well, his words are just remembered by others, he never wrote them down...)

With fixed-point arithmetic we can choose the precision of the numbers, because we can distribute bit usage between fractional and integer parts of a fixed number in any way we like. So, we can adapt a very fast code to very different accuracy demands.

In fixed-point, the simple integer division is the worst basic operation, because it loses precision the most. To somewhat remedy that, we can use multiplication by the reciprocal of that number (1/number) instead. To whet your appetite for fast and effective fixed point ASM code, I show a way to divide by 10 with faster, more efficiently and·more accurately, than·with the discussed acceleration method.

quotient = ((some_fixpoint >> 1) + some_fixpoint) >> 1 quotient = ((quotient >> 4) + quotient) quotient = ((quotient >> 8) + quotient) quotient = ((quotient >> 16) + quotient) >> 3 where 'some_fixpoint' can be any unsigned 32-bit number.

To make it even faster

quotient = ((some_fixpoint >> 1) + some_fixpoint) >> 1 quotient = ((quotient >> 4) + quotient) quotient = ((quotient >> 8) + quotient) >> 3 but 'some_fixpoint' here should be less (in integer format) than 534_890.

If you know other tricks or methods to speed up integer or fixed-point division or multiplication, let us know, too. SPIN or PASM test codes to check, improve or maybe to bust these ideas, are welcome.



Post Edited (cessnapilot) : 7/29/2009 7:10:30 PM GMT
2011/02/17 16:40 2011/02/17 16:40

A % B == 0인 게 알려져 있을 때 A / B를 곱셈 한 번(+ B가 짝수일 경우 시프트 한 번)으로 계산하는 방법은 알려져 있습니다(Z/(B)Z에 대한 B의 역수를 구해서 곱하면 됩니다). A가 임의의 숫자라면 A % B를 먼저 구해서 (A - A % B) / B를 구하는 방법을 쓸 수는 있는데, 이 경우에는 B가 작은 경우가 아니면 그다지 간단한 편은 아닙니다. Hackers' Delight 같은 책도 찾아 보세요.


감사합니다. 요즘에 개발로 보직을 변경해서.. 이제껏 좀 깊이 파고 들어가고 있습니다. 다만 스스로 찾아서 하려니 쉽지 않네요. 좋은 정보 감사합니다.

Filed under 주절주절
2011년이 된지도 벌써 24일이 지났습니다. 작년과 올해의 가장 큰 변화는 제 위치가 현재 "대기 발령" 상태라는 것입니다.

물론 나쁜 의미의 "대기 발령" 상태는 아닙니다. 저의 주 업무는 "System Engineering" 입니다. 대략 하던일은 OS 배포본 관리 및 system design 쪽을 맡고 있었는데, 사정에 의해 주업을 버리고 개발직으로 쫒겨나게 되었습니다.(희화해서 표현했습니다 ^^)

그러다 보니 현재 발령이 아직 나지 않아서 본의 아니게 "대기 발령" 상태로 있게 되었습니다.

생각해 보면 본업이 아닌 업무를 하게 되었지만, 제가 추구하던 System Engineering에는 Software Engineering 요소도 포함이 되어 있기 때문에 나쁜 기회라고 보이지는 않습니다만, 다만, 이를 주업으로 해야 하는 것이 아무래도 힘든 부분임은 분명합니다. 더군다나 표면적으로는 제 의지인 것 처럼 되어 있지만 아무래도 어쩔 수 없이 몰려서 선택해야 한 감도 있기 때문에 쉽지 않은 일은 분명할 것이고요. 그리고 결정적으로 앞에 4자를 달고 나니 어디 움직이기도 쉽지 않네요 ㅋㅋ

경력 15년차에 주 업무 변경이라는 큰 변화를 맞아 어떨지 기대반 겁반 입니다. 어떻게 잘 되겠죠 --;

며칠전 실장님이 "당신은 이제 SE가 아니라 개발자야!" 라고 화두를 주시더군요. 하지만 전 생각이 다릅니다. SE나 administration 측에서 개발에 아쉬웠던 부분을 개발에 전수를 하는 것이 제 몸값을 하는 것이 아닐까 싶기도 하고요. 아무래도 주업이 아닌 일을 하려고 하다 보면 몸값 문제가 분명히 나올테니 이에 대하 정의도 명확히 잘 해 둘 필요가 있을 듯 싶습니다.

결론적으로, 제 주업으로 다시 돌아갈 수 있을지 걱정(?)입니다. T.T 이 상태에서 이도 저도 아닌 상황이 되는건 아닌지.. 쩝.. 나이 40에 도전/모험 이라는 단어는 너무 남의 얘기로 들리는 군요 --; 그렇다고 개발을 잘 하는 것도 아니고 쩝..
2011/01/24 20:04 2011/01/24 20:04

안녕하세요, 장원석입니다.

전에 시스템엔지니어 학원을 다닐 때
리눅스 배포판 종류를 조사하다가 리눅스 이름이 특이해서
살펴보러 온 적이 있었는데...

개발자이신줄 알았는데, 시스템 엔지니어링과
시스템 디자인까지 하시는군요...

전 이제 막 걸음마 상태라 김정균님의 그런 스킬이
부럽기만 합니다.

oops.org 는 예전에 리눅스 공부할 때 openvpn 자료가 잘 나와있어서
가끔 왔었는데....

컴퓨터 조립이랑 리눅스, 윈도우 공부할 때
'니가 이기나, 내가 이기나 해보자' 하면서
될 때까지 몇시간씩, 며칠씩 매달리고 그랬는데...ㅎㅎ

아직 한참을 전 더 배워야하겠네요.

가끔 와서 시스템엔지니어 선배님의 멋진 선전 기대하고 응원하겠습니다.


Filed under 주절주절
현재 KLDP 접속이 되지를 않고 있습니다. 이유인즉, KLDP의 domain이 CDNetworks에서 제공하는 people.kldp.org 서버에서 운영 중인데, CDNetworks 사정으로 서버를 옮겨야 하는 상황이 되었고, IP가 변경이 된다고 합니다.

문제는 제가 요즘 좀 바쁜 관계로 한 일주일 개인 메일을 보지를 못했는데, 이 동안 연락이 왔다는 것입니다. 그래서 메일을 놓쳤고 CDNetworks에서는 오늘 장비를 이동을 한 모양입니다. 뭐, 제 불찰 입니다. 메일만 봤어도.. 최소 시간에 처리가 될 것이고 공지도 나갈 수 있었을텐데 말이죠.

현재 DNS가 죽은 상태라 메일/site 접속 등 되는 것이 아무것도 없습니다.

서버가 살아나더라도 DNS IP를 변경해야 하는 관계로 대략 4-5일 정도는 정상적인 서비스가 불가능 할 것 같군요. 어찌되었든 불편을 드려서 죄송하게 생각 합니다.
2010/12/22 15:46 2010/12/22 15:46

오늘 kldp가 접속이 되지 않고 있어서..도메인 만료가 되어서 그런줄 알고서..혹시나 하고 여기에 들어왔는데, 이렇게나마 답답한 맘을 알수가 있어서 좋네요..
고생이 정말 많으시네요..빨리 정상 복구가 되었음 합니다.

추운날 건강 조심하세요..^^


일단 서버 IP 변경하고, DNS host ip도 변경을 했습니다만.. 언제 변경이 완료될지는 기약이 없습니다. 일단 hosts 파일에 kldp.org

와 같이 등록을 하면 서비스를 이용할 수는 있습니다. T.T

Filed under 둘째 사고 일지
T.T 며칠 지났지만, 8/17 20:30 경.. 야구 방방이로 LCD 판넬을 깨버렸다. 수리비만 49만 8천원..
점점 미쳐가나 보다.
2010/11/19 17:42 2010/11/19 17:42
Filed under 둘째 사고 일지
둘째가 사고 치는 걸 기록하기로 했다. 도저히 못참겠어서.. 기록해 놓고 나중에.. 다 물어내라고 해야 핟 듯..

오늘은 형아가 게임하고 있는데, 컵에 물을 가득 받아서 노트북 키보드에 한 컵컵을 다 부어 버렸다. 순식간에 노트북 파워가 나가고 아마도 쇼트가 난 듯..

일주일 전에 Warranty 기간이 끝난는데.. --;
2010/11/16 00:12 2010/11/16 00:12

아.. 제 가슴이 다 아프네요. 침수는 사용자 과실 처리되기 쉽지만, 게다가 워런티도 끝나다니..

Filed under 주절주절
지인께서 이제 블러그 관리 안하시냐고 물어 보시길래.. 글 올린지가 꽤 되었구나 해서.. 일단 근황을 한번 올려 봅니다.

요즘은 다들 twitter를 이용하여 근황 관리를 하시던데, 전 왠지 me2day도 그렇고 twitter도 그렇고 별로 와닿지를 않습니다. 그리고 blog도 관리를 못해서 허덕이는데, 또 다른것을 펼치기도 그렇고 해서.. 사용하고 있지 않습니다. 그러니 근황도 blog를 통해서 하게 되는 군요.

요즘 초 필살 살인 스케줄에 시달리고 있습니다. D-day가 5일 남았는데(주말 빼면 3일 남았죠), 아직 정해진 것이라고는 D-day는 08/18 이다.. 입니다. T.T 10년을 넘게 일하면서 이런 스케줄은 정말 돌아버리겠군요. 요즘은 메일을 보면 메일의 문자가 한글이라는 것만 인식이 될 정도로 인지력까지 떨어진 상태입니다.

그러다 보니, TB 3.0 작업도 못하고 (석찬님이 대신 해 주셨습니다.) 못한다고 연락도 못드렸군요. 더불어 안녕 리눅스 2.0 작업도 석달때 손 놓고 있는 상황 (이건.. 머 몇 년전 부터이니.. 새삼스럽지도 않지만 ^^)

이 프로젝트가 앞으로도 3달 정도는 더 확장될 예정인데.. 요즘은 정말 좌절 스럽습니다. 같이 근무하던 분이 휴가 쓰신다고 하시니까 화가 나더군요 :-)
2010/08/13 21:26 2010/08/13 21:26

우연찮게 구글링하다가

정균님의 블로그까지 들르게 되었네요!

프로젝트가 끝나면 정균님께서도 휴가를 쓰시는 것이 좋을듯 합니다. :-)

건강하시고 일교차가 큰 가을입니다. 감기조심하시구요!

항상 감사합니다!


하하 쓰신 글보고 정말 격려해드려야겠다 싶어서 댓글쓰게 되네요.

예전에 oops.org 부지런히 다니면서 정균님 주시는 정보때문에
정말 어려운 고비 많이 넘겼습니다. 이제서야 감사드리네요.

좌절스럽다는 표현에서 상황은 예상이 됩니다만 건투를 빕니다~

Filed under Tech/Mozilla
이번에는 이전 "Firefox 확장에서 New Tab POST/Referrer 제어"에 이어 New Window로 POST data제어와 Refferer를 제어하는 방법에 대해서 논하도록 하겠습니다.

보통 javascript 에서 새 창을 띄울 경우 windows.open을 사용합니다. Firefox extension에서도 마찬 가지 입니다. 하지만 windows.open을 이용할 경우, referrer를 제어할 수가 없습니다. 또한 Post data를 제어를 하려면 상당히 귀찮습니다. --; Post data를 제어하는 예제를 보시죠.

window.open으로 새 창으로 열기

이 코드는 javascript 에서도 아마 사용이 가능 할 겁니다. 하지만, 얼마나 괴로울까요? 일단 about:blank로 새 창을 열고, 이 창에 DOM을 이용해서 form을 생성 시켜서 데이터를 post 또는 get으로 제어를 해야 합니다.

Translate To Korean 재작성을 하면서 Post 데이터를 처리하기 위해서 열라 검색을 해서 이런 코드를 만들었는데, referrer 처리도 안되고 openNewTabWith 와 object 호환도 안되서 코드가 난장 직전까지 가다 보니, 도저히 이렇게 사용을 할 수는 없겠더군요. 그래서 역시 Firefox source를 또 뒤져 보았습니다.

역시나, openNewTabWith API 아래에 openNewWindowWith라는 API가 존재를 하는 군요. openNewTabWith API 처럼 Post와 referrer를 모두 제어할 수 있도록 되어 있습니다. 그런데 문제는 창 속성을 지정을 할 수 있는 인자가 없습니다. 즉 무조건 새창을 현재창 크기로 띄워야만 하는 군요. 그래서 API 코드를 열어서 어떻게 사용하는지를 확인해 보았고 다음과 같은 코드를 만들어 낼 수 있었습니다.

Firefox API로 새 창으로 열기

2010/02/17 12:53 2010/02/17 12:53
Filed under Tech/Mozilla
요즘 Translate To Korean을 rewrite 하고 있습니다. 이번 작업에서 두가지를 처리하려고 하는데 하나는 GET으로 정보를 전달 하던 것을 POST method를 이용할 수 있도록 하는 것과, referer로 막는 것을 방지하기 위하여 referer를 처리할 수 있도록 하고 있습니다.

Firefox에서 이미 이를 위한 API를 제공하는데, 이에 대한 문서가 충분하지 않아 기록을 합니다.

새 탭으로 열기

2010/02/17 12:26 2010/02/17 12:26
Filed under Tech/Mozilla
제가 관리하고 있던 "Translate To Korean" Firefox 확장이 드디어 http://addons.mozilla.org의 sendbox를 탈출하게 되었습니다. 작년에 한번 시도했다가 code review에서 고배를 먹고, 이번에 Worldlingo 번역 URL이 변경되어 이를 수정하다가, 코드를 다시 가이드대로 재작성 하여 제출을 했었는데, 오늘 Congratulations 메일이 왔습니다.

sandbox 탈출의 의미는 현재 부가기능에서 업데이트 찾기가 되지 않는 문제가 Mozilla Addons 를 통해서 가능해 졌다는 점이 가장 의미가 있겠네요.

앞으로 Translate To Korean을 관리하던 http://oops.org/project/Firefox/Extension/translatekorean/ 은 유지하지 않고, Mozilla Addon에서 정식으로 유지를 하는 것으로 하려고 합니다. 그리고 여기서 받은 버전은 Mozilla Addons 사이트에서 받으신 것으로 설치를 해야지 업데이트 찾기가 가능해 집니다.

아래는 메일 전문 입니다. :-)

Congratulations! Your nominated add-on, Translate to Korean, has been reviewed by a Mozilla Add-ons editor who approved your add-on to be public.

Your most recent version (1.7.0) has also been made public.

You can view your public add-on now at: http://addons.mozilla.org/addon/7919

Review Information:
Reviewer: Raymond Lee
Comments: Congratulations, your add-on has been approved for public status. Due to caching and mirroring of AMO, it may take a couple of hours for your add-on to appear public, so please be patient.

Keep up the good work!

If you have questions about this review, please reply to this email or join #addons on irc.mozilla.org.

Mozilla Add-ons

2010/02/10 15:58 2010/02/10 15:58

한분의 노력으로 이렇게 결실을 맺게 되어 정말 축하할일이네요..
종종 오지만 많은걸 배우고..이렇게나마 댓글로 응원합니다.

이런 축하글들이 많이 올라오고, 도움을 주고 받는다면 더 좋은 한글 지원 addon들이 많이 나오지 않을까요..

고생많이 하셨습니다.

정말 축하합니다. :)

Filed under Tech/Tip & Trick
노트북도 하나 사고, 덩달아 Windows 7 Machine이 하나 생기게 되었습니다. OS를 64bit로 신청했는데 32bit로 온것 빼고는 그리 나쁘지 않더군요. 연말까지 휴가고 해서 회사 notebook을 과감히 Windows 7 64bit로 설치를 해 버렸습니다.

그런데 난리가 나 버렸군요.

제가 사용하는 환경은 Windows 기반에 cygwin + hanterm-xf 또는 portable ubuntu 환경을 사용합니다. 그런데 일단 Cygwin + hanterm-xf환경에서.. Windows 7에서 run.exe를 실행 할 때 cmd 창이 hidden 처리가 되어야 하는데, 되지를 않는 문제가 있더군요. 즉, hanterm 창 하나에 cmd 창이 하나씩 따라 열립니다. --; (엄격히 말하면 cmd 창이 열려서 hanterm-xf.exe를 실행하고 닫혀야 하는데 - 이게 run.exe가 하는 일이죠.) 그래서 이젠 오랫동안 사용한 cygwin + hanter-xf 환경은 버리고, portable ubuntu에 정착을 하자고 마음을 먹고 있었는데.. Windows 7 64bit 에서 colinux가 동작하지 않는다는 것을 까먹고 있었습니다. 그래서 어떡하든 cygwin을 해결해야 하는 상황이 되었습니다.

일단 cygwin homepage를 보니 cygwin 1.7 부터 Windows 7을 지원한다고 하고, 11월 말이나 12월 초에 릴리즈 할 거라고 적어 놓고선.. 왜 안하고 있지 하고 열심히 기다리고 있는데, 어제부로 cygwin 1.7이 릴리즈 되어 얼씨구나 하고 업데이트를 했지만 동일한 증상이 나타나더군요.

열심히 googling을 하다 보니.. 이미 메일링 리스트(http://www.cygwin.com/ml/cygwin-apps/2009-08/msg00018.html)에 이슈가 되어 있었으나, 개발자는 해당 패치를 거부한 모양 입니다. 혹시나 싶어서 이 패치를 적용해 보니.. ㅎㅎ 잘 되더군요.

혹시 비슷한 문제를 겪으시는 분들을 위해서.. 포스팅 합니다. 해당 패치가 된 run package는 ftp://mirror.oops.org/pub/Cygwin/pcakages/run/ 에서 받으실 수 있습니다. (웹 브라우저로 접근이 잘 안될 겁니다. ftp client를 이용하세요.) Windows 7 이 아닌 경우에는 받으실 필요 없습니다.

받으신 후에

shell> tar xvfpj run-1.1.12-11.tar.bz2 -C /

명령으로 설치가 가능 합니다. (한마디로 덮어 씌우는 거죠 ^^)
2009/12/24 03:01 2009/12/24 03:01