text:
# KD-Tree nodes in 4 bytes

This topic is 4925 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Ive been thinking about ways to reduce nodes in a kd tree (as applying to raytracing, but it goes for toher applications just aswell i beleive) to 4 bytes in size, halving them from the currently widely used 8 bytes. three improvements ive come up with: - a node is either a leaf or has one out of three splitaxis specified. thats four states, so two bits needed, not the commonly used 3. - you dont need nearly as much bits for a childpointer as are commonly used. its really simple: if your tree has 64k nodepairs, so 128k nodes (not a small tree), you need only 16 bits to differentiate between them. just multiply this value by the size of a nodepair to get the offset of the rootnode, + rootnode is memory adress. however, it can be done even better by using relative pointers, specifying the distance a child is away from its parent. again using 16 bits as an example, a parent and its leaf are constrained to being 128k nodespairs apart. without any clever node reorginization, just a naive 'sort all nodes by treepdeth', this would mean the maximum width of the tree would be 128k nodes. if kdtrees were balanced this would mean a maximum of 256k nodes, however, they are highly unbalanced, meaning much deeper and hence less broad, so this figure will be highly stretchable. i suspect 1M nodes wouldnt be any problem, but this requires some testing. also a tree can be built so as to limit width. - again using 16 bits as an example for pointer data, that leaves us with 14 bits for the splitplane position. as the clever reader notes: you cant fit a float in there :). however, 14 bits is still a resolution of 16k nonetheless. thats still a lot better than an octree with its resolution of 2, and not much worse than a float can provide, with its anisotropic resolution. (a float can only guarantee 7 digits of precision (correct me if im wrong), which isnt much worse than 5.) also, each splitplane could be specified relative to its parent, yielding a much better resolution at the lower levels of the tree, where precise positioning actually matters. so it seems that with some adaptation its quite possible to halve the memory needed for your tree. there is one main point of concern i have though: fixed point math & the splitplane position. i must say im not too familiar with the precise details of it, and if its possible without completely castrating your traversal speed. or would it for example be possible to interpret these 14 (or more for trees which need smaller maximum depth) as the most significant bits of a floats mantissa? or if that doesnt work is there another way to store only part of a float, discarding some precision? also im aware of the problem of specifying a splitplane at lower resolution than that of your vertex coordinates. however, this can be taken into account during tree construction: if the resolution of the position of a plane is too low to determine if an AABB falls on one side or the other, it simply falls in both. it slightly compromises the efficiency of your tree, but: -once again, it still beats octrees hands down. -by doing this you also adress numerical instabilities (that a 32bit float splitplane position also suffers from) which can lead to uncorrecly missed triangles. namely a vertex will never again lie precisely on a splitplane, but always a distanceaway from it, providing a buffer for numerical instabilities. another (experimental) solution: store vertices in 16bit fixed. splitplane position should easily surpass that on leaflevel. since rays get transformed into model space in my implementation, accuracy shouldnt be a problem. however, fixedpoint mathagain might be. other experimental idea: make split position precision dynamic: ie, minimize and count the maximum number of bits needed per childpointer for each treelevel, and use all unneeded bits for the splitplane. that should yield very accurate splitplanes in most cases, and where it doesnt, well, youll still suffer some slightly less effienciently constructed trees. wow, thats a lot of rambling, and there are probably not even a handfull of people visiting these boards that care at all about this, but for those that do care and have taken the time to give this some thought: id love to hear your vision on this. i think the possibilities are promising, but maybe im overlooking something. is this even worth it, for instance? it must save some memory and memory bandwidth, aswell as improve cache performance, but there are probably some instructions extra needed here and there, especially concerning the fixed point math.

##### Share on other sites
Very interesting. I was wondering the same thing lately, but I hadn't though about it in this much detail.

I have got around 6 bytes per triangle average storage with my aabb tree. I'ts really not clever - the main idea is to store several tris at once ( 2 - 8 ) in a leaf, which amortizes the cost of the full 24-byte AABB at each node & leaf.

I could get it much smaller if I compressed the AABB, but its not a bottleneck right now...

##### Share on other sites
I posted once about how I store my kd nodes in 32 bits. I do the axis/leaf identifier in the lower 2 bits of the split-plane. If the low 2 bits specify 'leaf' then the upper 30 bits are an offset into a list of primitive indexes. The primitive indexes are specified by a count of the primitives in the leaf in the first entry, then a list of unsigned ints that point to the actual leaf data.

 _______________ ______  ______________ ______  ______________ ________| 30-bit offset | leaf || 30-bit offset| leaf || 30-bit split | x-axis | --------------- ------  -------------- ------  -------------- --------      |                  /      |                 /   ___|_____ _______ __/______ _____  | # prims | 0 1 2 | # prims | 2 4 |   --------- ------- --------- -----            /  /    \    ______/   \     .           /   |     \  /           \     .        [leaf] [leaf] [leaf] [leaf] [leaf]

and the children of the node stored at m_nodes are implicitly stored at left = m_nodes[2i] and right = m_nodes[2i + 1].

##### Share on other sites
i do the same thing for my leafs. nearly the same. i store the amount of primitives in a leaf also in the node itself. plenty of space, and it saves a dereference on empty nodes.

as for implicitly storing nodes: isnt that very memory AND cache inefficient? note that this is just my reasoning, i havnt tested this, but deeper down in the tree it hardly grows exponentionally, even more so, it should shrink in the deepest levels. youll have seas of empty space deep in your tree, and no cache coherency at all.

however, after posting this topic i had a similar idea. to reduce the amount of bits needed to specify an offset, you could, instead of specifying the distance from object to object, specify the distance from a trendline, for example j = 2*i, although i think j = i is better on average. if you store the widest level of the tree, you could use a varying trendline depending on wether its expectde to grow or shrink. that really should bring back the number of needed bits for a decent sized tree to something like 14 or so, leaving a nice 16 bits for splitplane location.

if you store vertices as 16bit short, you only need 16bit short splitplane positions anyway.

however, im still not sure about the fixed-point aspect of all the maths, and its speed in particular. maybe i should start a topic on that in the math forums.

##### Share on other sites
By tracking the aabb of a node while traversing the tree, you could use your 16-bits like this:

unsigned int nodeBits = m_nodes[currentNodeIndex]; // Upper 16 bits are the split position.float weight = float(splitIndex) * (1.0f / float(0xffffffff)); // Get the weight [0, 1]float splitPos = aabbMax[axis] * weight + aabbMin[axis] * (1.0f - weight); // Get the actual split-axis

You could probably ignore to clear the lower bits since they would only shift the position very little.

##### Share on other sites
Quote:
 Original post by Eelcoi store the amount of primitives in a leaf also in the node itself. plenty of space, and it saves a dereference on empty nodes....as for implicitly storing nodes: isnt that very memory AND cache inefficient? note that this is just my reasoning, i havnt tested this, but deeper down in the tree it hardly grows exponentionally, even more so, it should shrink in the deepest levels. youll have seas of empty space deep in your tree, and no cache coherency at all.

right, if the leaf is empty I save the offset as 0, so there is no dereference. And as for memory/cache efficient... that's 2 different questions. Yes, memory usage it is exponential, but even at the 20th level, it's 4 Megs. Beyond that it gets much less efficient. Phantomus talked about a 45-deep tree for Buddah... I don't have 128 Terabytes of RAM, so it's not an option for me :)

As for cache-efficient, that was the whole reason why I originally came up with this scheme. It allows to determine address of grandchildren nodes without dereferencing and prefetch way ahead of time. Also, grandchildren are stored consecutively in 32 bytes -- size of a cache-line, so they can all be prefetched in one call.

As it turned out, when I profiled with prefetching turned off, it really didn't spend any time stalling on d-cache. I'm honestly not sure why this is. I was kind of mad because it eliminated what I thought was a huge performance benefit of my design. Oh well.

##### Share on other sites
yeah, thats sort of what i was thinking. by specifying everything (memory locations and positions in space) relative to a parent, you can archieve the needed resolution in only a couple of bits. however, i think any casts to float ought to be avoided in your inner loop, so another method should be used i think.

for example, you could store 7 exponent bits and 9 mantissa bits to store a truncated float in the range 0-1.

thinking about the implicit storage of nodes again, i just realized a way to do it with minimal memory waste. say you have a treelevel i and j=i+1, with two indices in it, I, and J respectively. for each node in i, count how much leafs came before it in i. since leafs wont have children, you can then store semi-implicit pointers of the form J = j.start + 2*(I - nodesbeforeI). if you put all nodepairs which are both children at the end of a level, i think you could build huge trees with only a couple of bits.

##### Share on other sites
Quote:
Original post by ajas95
Quote:
 Original post by Eelcoi store the amount of primitives in a leaf also in the node itself. plenty of space, and it saves a dereference on empty nodes....as for implicitly storing nodes: isnt that very memory AND cache inefficient? note that this is just my reasoning, i havnt tested this, but deeper down in the tree it hardly grows exponentionally, even more so, it should shrink in the deepest levels. youll have seas of empty space deep in your tree, and no cache coherency at all.

right, if the leaf is empty I save the offset as 0, so there is no dereference. And as for memory/cache efficient... that's 2 different questions. Yes, memory usage it is exponential, but even at the 20th level, it's 4 Megs. Beyond that it gets much less efficient. Phantomus talked about a 45-deep tree for Buddah... I don't have 128 Terabytes of RAM, so it's not an option for me :)

As for cache-efficient, that was the whole reason why I originally came up with this scheme. It allows to determine address of grandchildren nodes without dereferencing and prefetch way ahead of time. Also, grandchildren are stored consecutively in 32 bytes -- size of a cache-line, so they can all be prefetched in one call.

As it turned out, when I profiled with prefetching turned off, it really didn't spend any time stalling on d-cache. I'm honestly not sure why this is. I was kind of mad because it eliminated what I thought was a huge performance benefit of my design. Oh well.

yeah id also think prefetching grandchildren would be a good idea.

but youre saying it basicly it didnt matter? was it only the prefetching that didnt help, or was the switch to 4 byte simply completely useless?

btw, even if there is no speed benefit, i still like the idea of fixed point math. i can never stand floats and the fact that their resolution isnt constant, whereas for such an application, it obviously should be.

##### Share on other sites
Quote:
 Original post by Eelcobtw, even if there is no speed benefit, i still like the idea of fixed point math. i can never stand floats and the fact that their resolution isnt constant, whereas for such an application, it obviously should be.

I'm not sure squeezing nodes to 32bits is a win. First, once you have accessed a node you've wasted an entire cache line for it, say 64 bytes (read locality matters more).

Then, and that's the biggest problem in my eye, when doing a traversal à la Wald you better have the distance computed as early as possible, because you have few cycles to waste on concurrent computation before you have to decide (that is, use that distance) where you're going.
Going from fixed point to float/vector is going to take time you don't have; unless you make an all fixed point raytracer :)

Btw there's a good reason to use 3+1 bits to encode the leaf flag and axis (like Wald pointed out): with the leaf bit as the msb you can just test for signedness to know if it's a node or a leaf.
Then if you store the axis in the lowest part, you just need a compact and with a small immediate to extract it and you don't need to shift/scale the offset before you use it.
Can't be more efficient computationnaly.

##### Share on other sites
Quote:
Original post by tbp
Quote:
 Original post by Eelcobtw, even if there is no speed benefit, i still like the idea of fixed point math. i can never stand floats and the fact that their resolution isnt constant, whereas for such an application, it obviously should be.

I'm not sure squeezing nodes to 32bits is a win. First, once you have accessed a node you've wasted an entire cache line for it, say 64 bytes (read locality matters more).

yeah that makes sense.

Quote:
 Then, and that's the biggest problem in my eye, when doing a traversal à la Wald you better have the distance computed as early as possible, because you have few cycles to waste on concurrent computation before you have to decide (that is, use that distance) where you're going.Going from fixed point to float/vector is going to take time you don't have; unless you make an all fixed point raytracer :)

does the smiley indicate you think thats a bad idea? note that im not a numerical guru, but i have the feeling floats are used far to widely, in applications where they shouldnt be. however, going fixed point is often considered a hassle, because everything is built around floats, for seemingly no other reason than that its assumed to be the better choice.

why would i want to store vertex positions as floats? i might want to do so for vertices in camera-space, where adaptive resolution makes sense, but i see no compelling reasons to let my coordinates in model space have a resolution of 2^128 near the origin, and a resolution +-120 orders of magnitude lower just one unit away from it. floats enable me to cover a huge range, but my model space (in which i perform all calculations) is very much a bounded domain, so any ability to specify positions beyond that are wasted bits.

Quote:
 Btw there's a good reason to use 3+1 bits to encode the leaf flag and axis (like Wald pointed out): with the leaf bit as the msb you can just test for signedness to know if it's a node or a leaf.Then if you store the axis in the lowest part, you just need a compact and with a small immediate to extract it and you don't need to shift/scale the offset before you use it. Can't be more efficient computationnaly.

yeah that makes sense from an efficiency POV. i was assuming simple operations like bitshifting and bitmasking could be scheduled away somehow, but i suppose thats a little optimistic.

so your conclusion is going 32bit is a waste of time? i certainly am inclined to say so after the input ive been given (for which id like to thank you all).

however, id still like to investigate the possibilities of fixed point tracing further. i have applied fixed point math to a raycaster once, but needless to say it was a little less time crititcal. i cant remember the specifics, but it was a huge speedboost in texture lookup/interpolation anyway, and in general, i dont see why it has to be slower, as long as you stay away from casts. and ofcource make sure your algorithms are stable with fixed point math under any circumstances, ie no overflows.

1. 1
Rutin
26
2. 2
3. 3
4. 4
JoeJ
18
5. 5

• 14
• 14
• 11
• 11
• 9
• ### Forum Statistics

• Total Topics
631757
• Total Posts
3002135
×


text:
# Angular Momentum of a sanding disk

1. Nov 15, 2007

### Destrio

A sanding disk with rotational inertia 1.22x10^-3 kgm^2 is attached to an electric drill whose motor delivers a torque of 15.8 Nm
a) find angular momentum
b) find angular speed of the disk 33.0ms after the motor is turned on.

L = Iω
τ = Iα

we can find angular acceleration with what we are given α = τ/I
but I'm completely stumped on how to find L without having time.
any hints?

thanks

2. Nov 15, 2007

### Staff: Mentor

Here's a hint: You are given the time!

3. Nov 15, 2007

### Ojizo88

lol man I stared at that over and over again and thought, "I must be misreading this...wheres the trick?"

But seriously, yes you are given the time. its "33.0ms" part

4. Nov 15, 2007

### Destrio

Haha, thanks
I realized from that that I can use the time to solve the first part of my problem.

L = Iω

L =τω/α
ω = αt
L =τt

that works

τt = Iω
ω = τt/I
which gives me 427m/s
but i need the answer in rev/min
im okay with seconds to minutes, but how do i convert meters to revolutions?
2pi?

5. Nov 15, 2007

### Ojizo88

If you can find its angular acceleration, then ( just like linear kinematics... ) its angular velocity is equal to its angular acceleration multiplied by the duration of the acceleration.

6. Nov 15, 2007

### Staff: Mentor

The units for ω are radians/sec, not m/s. One revolution equals $2 \pi$ radians.

7. Nov 15, 2007

### Destrio

woo i got it!

thanks

format: plain


text:
GMAT Question of the Day - Daily to your Mailbox; hard ones only

 It is currently 06 Dec 2019, 20:53

### GMAT Club Daily Prep

#### Thank you for using the timer - this advanced tool can estimate your performance and suggest more practice questions. We have subscribed you to Daily Prep Questions via email.

Customized
for You

we will pick new questions that match your level based on your Timer History

Track

every week, we’ll send you an estimated GMAT score based on your performance

Practice
Pays

we will pick new questions that match your level based on your Timer History

# If n is a positive integer and r is the remainder when (n - 1)(n + 1)

Author Message
TAGS:

### Hide Tags

Senior Manager
Status: Finally Done. Admitted in Kellogg for 2015 intake
Joined: 25 Jun 2011
Posts: 439
Location: United Kingdom
GMAT 1: 730 Q49 V45
GPA: 2.9
WE: Information Technology (Consulting)
If n is a positive integer and r is the remainder when (n - 1)(n + 1)  [#permalink]

### Show Tags

21 Jan 2012, 17:57
20
131
00:00

Difficulty:

75% (hard)

Question Stats:

59% (02:22) correct 41% (02:14) wrong based on 1178 sessions

### HideShow timer Statistics

If n is a positive integer and r is the remainder when (n - 1)(n + 1) is divided by 24, what is the value of r?

(1) n is not divisible by 2
(2) n is not divisible by 3

_________________
Best Regards,
E.

MGMAT 1 --> 530
MGMAT 2--> 640
MGMAT 3 ---> 610
GMAT ==> 730
Math Expert
Joined: 02 Sep 2009
Posts: 59587
Re: If n is a positive integer and r is the remainder when (n - 1)(n + 1)  [#permalink]

### Show Tags

21 Jan 2012, 18:12
106
73
If n is a positive integer and r is the remainder when (n-1)(n+1) is divided by 24, what is the value of r?

Plug-in method:

$$(n-1)(n+1)=n^2-1$$

(1) n is not divisible by 2 --> pick two odd numbers: let's say 1 and 3 --> if $$n=1$$, then $$n^2-1=0$$ and as zero is divisible by 24 (zero is divisible by any integer except zero itself) so remainder is 0 but if $$n=3$$, then $$n^2-1=8$$ and 8 divided by 24 yields remainder of 8. Two different answers, hence not sufficient.

(2) n is not divisible by 3 --> pick two numbers which are not divisible by 3: let's say 1 and 2 --> if $$n=1$$, then $$n^2-1=0$$, so remainder is 0 but if $$n=2$$, then $$n^2-1=3$$ and 3 divided by 24 yields remainder of 3. Two different answers, hence not sufficient.

(1)+(2) Let's check for several numbers which are not divisible by 2 or 3:
$$n=1$$ --> $$n^2-1=0$$ --> remainder 0;
$$n=5$$ --> $$n^2-1=24$$ --> remainder 0;
$$n=7$$ --> $$n^2-1=48$$ --> remainder 0;
$$n=11$$ --> $$n^2-1=120$$ --> remainder 0.
Well it seems that all appropriate numbers will give remainder of 0. Sufficient.

Algebraic approach:

(1) n is not divisible by 2. Insufficient on its own, but this statement says that $$n=odd$$ --> $$n-1$$ and $$n+1$$ are consecutive even integers --> $$(n-1)(n+1)$$ must be divisible by 8 (as both multiples are even and one of them will be divisible by 4. From consecutive even integers one is divisible by 4: (2, 4); (4, 6); (6, 8); (8, 10); (10, 12), ...).

(2) n is not divisible by 3. Insufficient on its own, but form this statement either $$n-1$$ or $$n+1$$ must be divisible by 3 (as $$n-1$$, $$n$$, and $$n+1$$ are consecutive integers, so one of them must be divisible by 3, we are told that it's not $$n$$, hence either $$n-1$$ or $$n+1$$).

(1)+(2) From (1) $$(n-1)(n+1)$$ is divisible by 8, from (2) it's also divisible by 3, therefore it must be divisible by $$8*3=24$$, which means that remainder upon division $$(n-1)(n+1)$$ by 24 will be 0. Sufficient.

Hope it's clear.
_________________
Director
Status: Been a long time guys...
Joined: 03 Feb 2011
Posts: 987
Location: United States (NY)
Concentration: Finance, Marketing
GPA: 3.75
Re: If n is a positive integer and r is the remainder when (n - 1)(n + 1)  [#permalink]

### Show Tags

31 Dec 2012, 21:18
5
1
If n is positive integer and r is the remainder when (n-1)(n+1) is divided by 24, what is the value of r?

(1) is not divisible by 2
(2) is not divisible by 3

Statement 1)
When n is not divisible by 2, then n can be $$1, 3, 5, 7, 9 etc$$
For n=1, the remainder is 0
For n=3, the remainder is 16.
For n=5, the remainder is 0.

statement 2)
When n is not divisible by 3, then n can be $$1,2, 4, 6 etc$$
Here also different remainders.
Insufficient.

On combining these two statements, n is $$1,5, 7 etc$$
For such numbers, the remainder is 0.
Sufficient.
+1C
_________________
##### General Discussion
Director
Joined: 22 Mar 2011
Posts: 584
WE: Science (Education)
Re: If n is a positive integer and r is the remainder when (n - 1)(n + 1)  [#permalink]

### Show Tags

26 Sep 2012, 13:44
1
ksharma12 wrote:
If n is a positive integer and r is the remainder when (n - 1)(n + 1) is divided by 24, what is the value of r ?

(1) n is not divisible by 2.

(2) n is not divisible by 3.

(1) n must be odd. Try n = 1 and n = 3.
Not sufficient.

(2) Try n = 1 and n = 2.
Not sufficient.

(1) and (2) together: When divided by 6, the remainders can be 0, 1, 2, 3, 4, 5. Since n is not divisible neither by 2, nor by 3, when divide by 6, n can give remainder 1 or 5, which means n is of the form 6k + 1 or 6k - 1, for some positive integer k.
If n = 6k + 1, then (n - 1)(n + 1) = 6k(6k + 2) = 12k(3k + 1) = 12k(k + 2k + 1). Since 2k + 1 is odd, k and 3k + 1 are of different parities, so their product is for sure divisible by 2. Altogether, (n - 1)(n + 1) is divisible by 24.
If n = 6k - 1, then (n - 1)(n + 1) = (6k - 2)6k)= 12k(3k - 1) = 12k(k + 2k - 1). Since 2k - 1 is odd, k and 3k - 1 are of different parities, so their product is for sure divisible by 2. Altogether, (n - 1)(n + 1) is divisible by 24.
The remainder must be 0.
Sufficient.

_________________
PhD in Applied Mathematics
Love GMAT Quant questions and running.
Retired Moderator
Joined: 05 Jul 2006
Posts: 1380
Re: If n is a positive integer and r is the remainder when (n - 1)(n + 1)  [#permalink]

### Show Tags

12 Jan 2013, 03:34
1
kiyo0610 wrote:
If n is a positive integer and r is the remainder when (n-1)(n+1)is divided by 24, what is the value of r?

(1) n is not divisible by 2
(2) n is not divisible by 3

n-1,n, n+1 are consecutive +ve intigers, and thus if n is even both n-1,n+1 are odd and vice versa. also in every 3 consecutive numbers we get one that is a multiple of 3

from 1

n is odd thus both n-1, n+1 are even and their product has at least 2^3 as a factor however if n = 3 thus n-1,n+1 are 2,4 and since , 24 = 2^3*3 , thus reminder is 3 but if n = 5 for example thus n-1,n+1 are 4,6 and therofre in this case r = 0.....insuff

from 2

n is a multiple of 3 and thus both n-1,n+1 are either even (e.g: n=3) or odd (n=6) and therfore this is insuff

both together

n is odd and is a multiple of 3 and therfore the reminder of the product (n-1)(n+1) when devided by 24 is always 3..suff

C
Veritas Prep GMAT Instructor
Joined: 16 Oct 2010
Posts: 9850
Location: Pune, India
Re: If n is a positive integer and r is the remainder when (n - 1)(n + 1)  [#permalink]

### Show Tags

25 Mar 2013, 21:02
7
1
vbodduluri wrote:
If n is a positive integer and r is the remainder when (n-1)(n+1) is divided by 24, what is the value of r?
a)n is not divisible by 2
b) n is not divisible by 3

A few things:
1. Exactly one of any two consecutive positive integers is even.
2. Exactly one of any three consecutive positive integers must be a multiple of 3
3. Exactly one of any four consecutive positive integers must be a multiple of 4
etc
Check this post for the explanation:
http://www.veritasprep.com/blog/2011/09 ... c-or-math/

a) n is not divisible by 2

Since every alternate number is divisible by 2, (n-1) and (n+1) both must be divisible by 2. Since every second multiple of 2 is divisible by 4, one of (n-1) and (n+1) must be divisible by 4. Hence, the product (n-1)*(n+1) must be divisible by 8. But if n is divisible by 3, then neither (n-1) nor (n+1) will be divisible by 3 and hence, when you divide (n-1)(n+1) by 24, you will get some remainder. If n is not divisible by 3, one of (n-1) and (n+1) must be divisible by 3 and hence the product (n-1)(n+1) will be divisible by 24 and the remainder will be 0. Not sufficient.

b) n is not divisible by 3
We don't know whether n is divisible by 2 or not. As discussed above, we need to know that to figure whether the product (n-1)(n+1) is divisible by 8. Hence not sufficient.

Take both together, we know that (n-1)*(n+1) is divisible by 8 and one of (n-1) and (n+1) is divisible by 3. Hence, the product must be divisible by 8*3 = 24. So r must be 0. Sufficient.

Another approach:

(n-1), n and (n+1) are consecutive integers.

If 2 is not a factor of n (i.e. n is odd), it must be a factor of (n-1) and (n+1) (the numbers around n must be even).
Also, out of any two consecutive even numbers, one has to be divisible by 4 because every alternate multiple of 2 is divisible by 4.
Hence, (n-1)*(n+1) must be divisible by 8.

Out of any 3 consecutive integers, one has to be divisible by 3 because every third integer is a multiple of 3. Out of (n-1), n and (n+1), one has to be divisible by 3. If n is not divisible by 3, one of (n-1) and (n+1) must be divisible by 3.
Hence, (n-1)*(n+1) must be divisible by 3.

Using both statements, (n-1)*(n+1) must be divisible by 8*3 = 24. Remainder must be 0.

_________________
Karishma
Veritas Prep GMAT Instructor

Director
Joined: 17 Dec 2012
Posts: 623
Location: India
Re: If n is a positive integer and r is the remainder when (n - 1)(n + 1)  [#permalink]

### Show Tags

Updated on: 26 Mar 2013, 02:15
vbodduluri wrote:
If n is a positive integer and r is the remainder when (n-1)(n+1) is divided by 24, what is the value of r?
a)n is not divisible by 2
b) n is not divisible by 3

Given:

(n-1)(n+1) = 24m + r - (1) where m=1,2,3...

Statement 1:

n = 2w + x - (2)

Statement 1 alone is not sufficient

Statement 2:

n= 3y + z - (3)

Statement 2 alone is not sufficient.

Taken together:

1. x has to be 1 and z can be 1 or 2

2. When x and z are 1, the values of n are 7, 13, 19 etc

3. When x=1 and z=2, the values of n are 5, 11, 17 etc

4. Substitute one of the above values, say 5 in (1)

5. For n=5 we have 4*6 = 24m + r or
24m +r = 24
r=0

We will get the same value of r for the other values of n too.

_________________
Srinivasan Vaidyaraman
Sravna Test Prep
http://www.sravnatestprep.com

Holistic and Systematic Approach

Originally posted by SravnaTestPrep on 26 Mar 2013, 00:50.
Last edited by SravnaTestPrep on 26 Mar 2013, 02:15, edited 3 times in total.
Director
Joined: 26 Oct 2016
Posts: 600
Location: United States
Schools: HBS '19
GMAT 1: 770 Q51 V44
GPA: 4
WE: Education (Education)
Re: If n is a positive integer and r is the remainder when (n - 1)(n + 1)  [#permalink]

### Show Tags

31 Jan 2017, 17:12
1) n not divisible by 2=> n is odd=> (n-1) and (n+1) must be consective even numbers.

if n=1, 0*2/24 leaves remainder 0
if n=3, 2*4/24 leaves remainder 8
not sufficient

2) n not divisible by 3=> n can be even or 1, 5, 7, 11, 13....

if n=5, 4*6/24 leaves remainder 0
if n=2, 1*3/24 leaves remainder 3
not sufficient

together,
n must be odd and not divisible by 3=> n can be 1, 5, 7, 11, 13...
if n=7, 6*8/24 leaves remainder 0
if n=11, 10*12/24 leaves remainder 0

hence C.
_________________
Thanks & Regards,
Anaira Mitch
Intern
Joined: 03 Apr 2014
Posts: 2
Re: If n is a positive integer and r is the remainder when (n - 1)(n + 1)  [#permalink]

### Show Tags

11 Sep 2017, 06:28
Bunuel

VeritasPrepKarishma

What if n=1?

If so, (n-1) will = 0.

Thank you.
Math Expert
Joined: 02 Sep 2009
Posts: 59587
Re: If n is a positive integer and r is the remainder when (n - 1)(n + 1)  [#permalink]

### Show Tags

11 Sep 2017, 06:32
Eff wrote:
Bunuel

lakshmi

What if n=1?

If so, (n-1) will = 0.

Thank you.

0 is divisible by every positive integer.
_________________
Manager
Joined: 30 Jul 2014
Posts: 106
GPA: 3.72
Re: If n is a positive integer and r is the remainder when (n - 1)(n + 1)  [#permalink]

### Show Tags

14 Sep 2017, 03:01
1
By combining both the statement, we know that if a number is a prime number apart from 2, and 3, then it can be written in the form of (6n+1) or (6n-1) - plugging these values, we get that (n-1)(n+1) is always a multiple of 24; hence sufficient. Answer C.
_________________
A lot needs to be learned from all of you.
GMAT Tutor
Joined: 24 Jun 2008
Posts: 1829
If n is a positive integer and r is the remainder when (n - 1)(n + 1)  [#permalink]

### Show Tags

02 Jun 2018, 18:09
enigma123 wrote:
If n is a positive integer and r is the remainder when (n - 1)(n + 1) is divided by 24, what is the value of r?

(1) n is not divisible by 2
(2) n is not divisible by 3

* n-1, n and n+1 are three consecutive integers, so one of them must be a multiple of 3, since every third integer is a multiple of 3. From Statement 2, n is not a multiple of 3, so one of n-1 or n+1 is.

* If, from Statement 1, n is odd, then n-1 and n+1 are even. Since every second even number is a multiple of 4, one of n-1 and n+1 is a multiple of 4 (at least) and the other a multiple of 2. So (n-1)(n+1) is a multiple of 8.

So with both Statements together we know that (n-1)(n+1) is a multiple of 3 and 8, and therefore of 24, and the remainder is zero.
_________________
GMAT Tutor in Toronto

If you are looking for online GMAT math tutoring, or if you are interested in buying my advanced Quant books and problem sets, please contact me at ianstewartgmat at gmail.com
Director
Joined: 14 Dec 2017
Posts: 509
Location: India
Re: If n is a positive integer and r is the remainder when (n - 1)(n + 1)  [#permalink]

### Show Tags

15 Jun 2018, 08:30
enigma123 wrote:
If n is a positive integer and r is the remainder when (n-1)(n+1) is divided by 24, what is the value of r?

(1) n is not divisible by 2
(2) n is not divisible by 3

Given , n > 0, r is remainder when (n-1)(n+1) is divided by 24, r = ?

(n-1)(n+1) is the product two consecutive even or odd integers, depending on whether n is odd or even.

Statement 1: n is not divisible by 2

n = odd, then we have, for n = 3, (n-1)(n+1) = (3-1)(3+1) = 8, hence r = 8
for n = 5, (n-1)(n+1) = (5-1)(5+1) = 4*6 = 24, hence r = 0

Statement 1 alone is Not Sufficient.

Statement: n is not divisible by 3.
hence, for n = 5, we have from above r = 0
& for n = 8, we have (n-1)(n+1) = (8-1)(8+1) = 7*9 = 63, hence r = 15

Statement 2 alone is Not Sufficient.

Combining the two statements, we get, n is not divisible by 2 or 3
for n = 7, (n-1)(n+1) = (7-1)(7+1) = 6*8 = 48, hence r = 0
for n = 11, (n-1)(n+1) = (11-1)(11+1) = 10*12 = 120, hence r = 0

Both Statements together are Sufficient.

Thanks,
GyM
_________________
Manager
Joined: 04 Jun 2017
Posts: 109
Location: India
Concentration: Strategy, Operations
GMAT 1: 500 Q39 V20
GPA: 3.82
Re: If n is a positive integer and r is the remainder when (n - 1)(n + 1)  [#permalink]

### Show Tags

25 Jun 2019, 09:57
Statement 1)
When n is not divisible by 2, then n can be 1,3,5,7,9
For n=1,3 & 5 , Different answers. Hence insufficient.

statement 2)
When n is not divisible by 3, then n can be 1,2,4,etc
Here also different remainders.
Insufficient.

On combining these two statements, n is 1,5,7
For such numbers, the remainder is 0.

C is Correct
Non-Human User
Joined: 09 Sep 2013
Posts: 13724

### Show Tags

20 Oct 2019, 02:07
Hello from the GMAT Club BumpBot!

Thanks to another GMAT Club member, I have just discovered this valuable topic, yet it had no discussion for over a year. I am now bumping it up - doing my job. I think you may find it valuable (esp those replies with Kudos).

Want to see all other topics I dig out? Follow me (click follow button on profile). You will receive a summary of all topics I bump in your profile area as well as via email.
_________________
Re: ds#positive integer   [#permalink] 20 Oct 2019, 02:07
Display posts from previous: Sort by


text:
## Monetising the side bets

If you were to read Matt Levine’s excellent newsletter regularly, you might hypothesize that the market for Credit Default Swaps (CDS) is dying. Every other day, we see news of either engineered defaults (companies being asked to default by CDS holders in exchange for cheap loans in the next round), transfer of liability from one legal entity to another (parent to subsidiary or vice versa), “orphaning” of CDSs (where on group company pays off debt belonging to another) and so on.

So what was once a mostly straightforward instrument (I pay you a regular stream of money, and you pay me a lumpsum if the specified company defaults) has now become an overly legal product. From what seemed like a clever way to hedge out the default risk of a loan (or a basket of loans), CDSs have become an over-lawyered product of careful clauses and letters and spirits, where traders try to manipulate the market they are betting on (if stuff like orphaning or engineered default were to happen in sports, punters would get arrested for match-fixing).

One way to think of it is that it was a product that got too clever, and now people are figuring out a way to set that right and the market will soon disappear. If you were to follow this view, you would thin that ordinary credit traders (well, most credit traders work for large banks or hedge funds, so not sure this category exists) will stop trading CDSs and the market will die.

Another way to think about it is that these over-legalistic implications of CDSs are a way by the issuer of the debt to make money off all the side bets that happen on that debt. You can think about this in terms of horse racing.

Horse breeding is largely funded by revenues from bets. Every time there is a race, there is heavy betting (this is legal in most countries), and a part of the “rent” that the house collects from these bets is shared with the owners of the horses (in the form of prizes and participation fees). And this revenue stream (from side bets on which horse is better, essentially) completely funds horse rearing.

CDSs were a product invented to help holders of debt to transfer credit risk to other players who could hedge the risk better (by diversifying the risk, owning opposite exposures, etc.). However, over time they got so popular that on several debt instruments, the amount of CDSs outstanding is a large multiple of the total value of the debt itself.

This is a problem as we saw during the 2008 financial crisis, as this rapidly amplified the impacts of mortgage defaults. Moreover, the market in CDSs has no impact whatsoever on the companies that issued the debt  – they can see what the market thinks of their creditworthiness but have no way to profit from these side bets.

And that is where engineered defaults come in – they present a way for debt issuers to actually profit from all the side bets. By striking a deal with CDS owners, they are able to transfer some of the benefits of their own defaults to cheaper rates in the next round of funding. Even orphaning of debt and transferring between group companies are done in consultation with CDS holders – people the company ordinarily should have nothing to do with.

The market for CDS is very different from ordinary sports betting markets – there are no “unsophisticated players”, so it is unclear if anyone can be punished for match fixing. The best way to look at all the turmoil in the CDS market can thus be looked at in the same way as horse rearing – an activity being funded by “side bets”.

## Advertising Agencies: From Brokers to Dealers

The Ken, where I bought a year long subscription today, has a brilliant piece on the ad agency business (paywalled) in India. More specifically, the piece is on pricing in the industry and how it is moving from a commissions only basis to a more mixed model.

Advertising agencies perform a dual role for their clients. Apart from advising them on advertising strategy and helping them create the campaigns, they are also in charge of execution and buying the advertising slots – either in print or television or hoardings (we’ll leave online out since the structure there is more complicated).

As far as the latter business (acquisition of slots to place the ad – commonly known as “buying”) is concerned, typically agencies have operated on a commission basis. The fees charged has been to the extent of about 2.5% of the value of the inventory bought.

In financial markets parlance, advertising agencies have traditionally operated as brokers, buying inventory on behalf of their clients and then charging a fee for it. The thrust of Ashish Mishra’s piece in ate Ken is that agencies are moving away from this model – and instead becoming what is known in financial markets as “dealers”.

Dealers, also known as market makers, make their money by taking the other side of the trade from the client. So if a client wants to buy IBM stock, the dealer is always available to sell it to her.

The dealer makes money by buying low and selling high – buying from people who want to sell and selling to people who want to buy. Their income is in the spread, and it is risky business, since they bear the risk of not being able to offload inventory they have had to buy. They hedge this risk by pricing – the harder they think it is to offload inventory, the wider they set the spreads.

Similarly, going by the Ken story, what ad agencies are nowadays doing is to buy inventory from media companies, and then selling it on to the clients, and making money on the spread. And clients aren’t taking too well to this new situation, subjecting the dealers ad agencies to audits.

From a market design perspective, there is nothing wrong in what the ad agencies are doing. The problem is due to their transition from brokers to dealers, and their clients not coming to terms with the fact that dealers don’t normally have a fiduciary responsibility towards their clients (unlike brokers who represent their clients). There are also local monopoly issues.

The main service that a dealer performs is to take the other side of the trade. The usual mechanism is that the dealer quotes the prices (both buy and sell) and then the client has the option to trade. If the client feels the dealer is ripping her off, she has a chance to not do the deal.

And in this kind of a situation, the price at which the dealer obtained the inventory is moot – all that matters to the deal is the price that the dealer is willing to sell to the client at, and the price that competing dealers might be charging.

So when clients of ad agencies demand that they get the inventory at the same price at which the agencies got it from the media, they are effectively asking for “retail goods at wholesale rates” and refusing to respect the risk that the dealers might have taken in acquiring the inventories (remember the ad agencies run the risk of inventories going unsold if they price them too high).

The reason for the little turmoil in the ad agency industry is that it is an industry in transition – where the agencies are moving from being brokers to being dealers, and clients are in the process of coming to terms with it.

And from one quote in the article (paywalled, again), it seems like the industry might as well move completely to a dealer model from the current broker model.

Clients who are aware are now questioning the point of paying a commission to an agency. “The client’s rationale is that is that it is my money that is being spent. And on that you are already making money as rebate, discount, incentive and reselling inventory to me at a margin, so why do I need to pay you any agency commissions? Some clients have lost trust in their agencies owing to lack of transparency,” says Sodhani.

Finally, there is the issue of monopoly. Dealers work best when there is competition – the clients need to have an option to walk away from the dealers’ exorbitant prices. And this is a bit problematic in the advertising world since agencies act as their clients’ brokers elsewhere in the chain – planning, creating ads, etc.

However the financial industry has dealt with this problem where most large banks function as both brokers and dealers. It’s only a matter of time before the advertising world goes down that path as well.

PS: you can read more about brokers and dealers and marketplaces and platforms in my book Between the Buyer and the Seller

## Investing in ETFs

So I put some money in an ETF today. This isn’t the first time I invested in one. A long time back, before my then employer had bought and essentially killed Benchmark, I had invested in a couple of their ETFs – the Nifty ETF to get invest in the broad Indian market, and GoldBees to hedge against increase in the price of gold as I was planning my wedding.

I had some Rupees lying around in my bank account for a long time, and given that the Indian markets have tanked, I thought this is a good time to get invested. In fact, this isn’t the first time in recent times I’m having such a thought – about a month back I had put in more money into the Indian markets, but had then chosen a low cost index tracking mutual fund (and I’m not tracking how my investment is doing).

Anyway, today I decided to invest in ETFs since the transaction costs (in terms of both trading, and annual expenses) are much lower. A quick chat with a friend currently trading the Indian markets revealed that the SBI Nifty ETF is the best option to go with, and I was left with the small matter of just making the investment.

I’m generally happy with ICICI Direct as my broker, since in general the interface and app are pretty nice. Last month, the purchase of the mutual fund through the same app had been pretty simple. And I imagined buying the ETF will be easy as well. It wasn’t. And if I, as a professional investor with considerable capital markets experience, find it hard to invest in ETFs, I can only imagine how hard it might be for mango people to invest in them.

So the points of pain, in order, that prevent people from investing in ETFs:

1. Knowing that indexing exists. Most people seem to think that the only ways to invest are by researching the stocks themselves, or by paying an asset manager fairly hefty fees.
2. Once you know you can index, the fact that you can do it through an ETF. ETFs are again not well known, and not really marketed broadly since their fees are low (with Benchmark’s demise, we don’t really have ETF-first fund houses in India, like we have Vanguard in the US).
1. Related, even some of the more popular robo advisory funds in India largely use mutual funds, rather than ETFs.
3. Once you know you can index, and do so through an ETF, the next task is to find out which ETF you should invest in. Literature exists, but is not easy to find. My friend sent me this page, and asked me to select the fund with highest market size. Knowing that I want to invest in the broad market, and in large caps, the choice of SBI Nifty ETF was easy for me.
1. But it’s not so intuitive for a less sophisticated investor. For example, correlating asset size with liquidity isn’t exactly intuitive.
2. Different ETFs track different indices, and knowing which one to invest in is again not a trivial task.
4. Having selected an ETF to invest in, you go to your broker’s site or app (I used the app). And you need to know that ETFs are clubbed with equities, and not with mutual funds (not an intuitive classification for most people)
5. So I go to ICICI Direct’s Equities page, allocate funds to it (from my bank account, also with ICICI), and hit “buy”. There’s a text box where I need to enter what I’m looking for, and then there’s a dropdown that pops up.

I type “SBI”, and the first thing it shows is the SBI Bank Nifty tracker. This is followed by lots of bonds. I don’t know if it’s clever nudging on ICICI’s part to get you to invest in the Bank Nifty, since that has a significant exposure to ICICI, or if it’s something as mundane as alphabetical sorting. The latter is more likely.

6. Scrolling down the list past all the bonds, it’s not easy to know which is the SBI Nifty ETF. Because there’s a “SBI Nifty Next 50 ETF” (smaller caps, so more volatile, not something I want), and a few others with confusing names.
7. Then you need to enter the number of units you need to purchase. This is unlike in mutual funds where you just enter the amount you want to invest. Here I had to pull up a calculator to know exactly how many units I had to buy.
8. I hit “market order”, and then on the next screen I got a warning that since this wasn’t a particularly liquid instrument I was only allowed to post limit orders. So I had to guess what was a reasonable spread I was willing to pay, and put that. Thankfully the ETF was fairly liquid, and I got execution close to mid.

Honestly, I felt rather daunted at the end of the exercise, and I’m what most people would classify as a sophisticated investor. So there is no wonder that more people aren’t investing in ETFs.

The advantage of ETFs is extremely low fees (the fund I purchased today charges 7 basis points a year), and one downside of it is that it doesn’t allow for more marketing budget.

I’m beginning to think that the way to “solve” this market is by having a bundled ETF and robo advisory offering. Perhaps more on that later.

## Suckers still exist

1. You give Citigroup Inc. $1,000, when Amazon.com’s stock is at$1,339.60.
2. At the end of each quarter for the next three years, Citi looks at Amazon’s stock price. If it’s at or below $1,339.60, Citi sends you$25 and the trade continues. If it’s above $1,339.60, Citi sends you back your$1,000 and the trade is over.
3. At the end of the three years, Citi looks at Amazon’s stock price. If it’s above $1,004.70 (75 percent of the initial stock price), then Citi sends you$1,025 and the trade is over. But if it’s below $1,004.70, you eat the full amount of the loss: For instance, if Amazon’s stock price is$803.80 (60 percent of the initial stock price), then you lose 40 percent of your money, and get back only $600. Citi keeps the rest. (You get to keep all the premiums, though.) Anyone with half a brain should know that this is not a great trade. For starters, it gives the client (usually a hedge fund or a pension fund or someone who represents rich guys) a small limited upside (of 10% per year for three years), while giving unlimited downside if Amazon lost over 25% in 3 years. Then, the trade has a “knock out” (gets unwound with Citigroup paying back the client the principal) clause, with the strike price of the knockout being exactly the Amazon share price on the day the contract came into force. And given that Amazon has been on a strong bull run for a while now, it seems like a strange price at which to put a knock out clause. In other words, there is a high probability that the trade gets “knocked out” soon after it comes into existence, with the client having paid up all the transaction costs (3.5% of the principal in fees). Despite this being such a shitty deal, Levine reports that Citigroup sold$16.3 million worth of these “notes”. While that is not a large amount, it is significant that nearly ten years after the financial crisis, there are still suckers out there, whom clever salespersons in investment banks can con into buying such shitty notes. It seems institutional memory is short (or these clients are located in states in the US where marijuana is legal).

PS: Speaking of suckers, I recently got to know of the existence of a school in Mumbai named “Our Lady of Perpetual Succour“. Splendid.

## Dimensional analysis in stochastic finance

Yesterday I was reading through Ole Peters’s lecture notes on ergodicity, a topic that I got interested in thanks to my extensive use of Utility Theory in my work nowadays. And I had a revelation – that in standard stochastic finance, mean returns and standard deviation of returns don’t have the same dimensions. Instead, it’s mean returns and the variance of returns that have the same dimensions.

While this might sound counterintuitive, it is not hard to see if you think about it analytically. We will start with what is possibly the most basic equation in stochastic finance, which is the lognormal random walk model of stock prices.

$dS = \mu S dt + \sigma S dW$

This can be rewritten as

$\frac{dS}{S} = \mu dt + \sigma dW$

Now, let us look at dimensions. The LHS divides change in stock price by stock price, and is hence dimensionless. So the RHS needs to be dimensionless as well if the equation is to make sense.

It is easy to see that the first term on the RHS is dimensionless – $\mu$, the average returns or the drift, is defined as “returns per unit time”. So a stock that returns, on average, 10% in a year returns 20% in two years. So returns has dimensions $t^{-1}$, and multiplying it with $dt$ which has the unit of time renders it dimensionless.

That leaves us with the last term. $dW$ is the Wiener Process, and is defined such that $dW^2 = dt$. This implies that $dW$ has the dimensions $\sqrt{t}$. This means that the equation is meaningful if and only if $\sigma$ has dimensions $t^{-\frac{1}{2}}$, which is the same as saying that $\sigma^2$ has dimensions $\frac{1}{t}$, which is the same as the dimensions of the mean returns.

It is not hard to convince yourself that it makes intuitive sense as well. The basic assumption of a random walk is that the variance grows linearly with time (another way of seeing this is that when you add two uncorrelated random variables, their variances add up to give the variance of the sum). From this again, variance has the units of inverse time – the same as the mean.

Finally, speaking of dimensional analysis and Ole Peters, check out his proof of the Pythagoras Theorem using dimensional analysis.

Isn’t it beautiful?

PS: Speaking of dimensional analysis, check out my recent post on stocks and flows and financial ratios.

## Stocks and flows

One common mistake even a lot of experienced analysts make is comparing stocks to flows. Recently, for example, Apple’s trillion dollar valuation was compared to countries’ GDP. A few years back, an article compared the quantum of bad loans in Indian banks to the country’s GDP. Following an IPL auction a few years back, a newspaper compared the salary of a player the market cap of some companies (paywalled).

The simplest way to reason why these comparisons don’t make sense is that they are comparing variables that have different dimensionality. Stock variables are usually measured in dollars (or pounds or euros or whatever), while flows are usually measured in terms of currency per unit time (dollars per year, for example).

So to take some simple examples, your salary might be $100,000 per year. The current value of your stock portfolio might be$10,246. India’s GDP is 2 trillion dollars per year.  Liverpool FC paid £67 million to buy out Alisson’s contract at AS Roma, and will pay him a salary of about £77,000 per week. Apple’s market capitalisation is 1.05 trillion dollars, and its sales as per the latest financials is 229 billion dollars per year.

Get the drift? The simplest way to avoid confusing stocks and flows is to be explicit about the dimensionality of the quantity being compared – flows have a “per unit time” suffixed to their dimensions.

Following the news of Apple’s market cap hitting a trillion dollars, I put out a tweet about the fallacy of comparing it to the GDP of the United States.

A lot of the questions that followed came from stock market analysts, who are used to looking at companies in terms of financial ratios, most of which involve both stocks and flows. They argued that because these ratios are well-established, it is legitimate to compare stocks to flows.

For example, we get the Price to Earnings ratio by dividing a company’s stock price (a stock) by the company’s annual earnings per share (a flow). The asset turnover ratio is derived by dividing the annual revenues (a flow) by the amount of assets (a stock). In fact, barring simple ratios such as gross margin, most ratios in financial analysis involve dividing a stock by a flow or the other way round.

To put it simply, financial ratios are not a case of comparing stocks to flows because ratios by themselves don’t mean a thing, and their meaning is derived from comparing them to similar ratios from other companies or geographies or other points in time.

A price to earnings ratio is simply the ratio of price per share to (annual) earnings per share, and has the dimension of “years”. When we compute the P/E ratio, we are not comparing price to earnings, since that would be nonsensical (they have different dimensions). We are dividing one by the other and comparing the ratio itself to historic or global benchmarks.

The reason a company with a P/E ratio of 25 (for example) is seen as being overvalued is because this value lies at the upper end of the distribution of historical P/E ratios. So we are comparing one ratio to the other (with both having the same dimension).

In conclusion, when you take the ratio of one quantity to another, you are just computing a new quantity – you are not comparing the numerator to the denominator. And when you compare quantities, always make sure that you are being dimensionally consistent.

## A one in billion trillion event

It seems like capital markets quants have given up on the lognormal model for good, for nobody described Facebook’s stock price drop last Thursday as a “one in a billion trillion event”. For that is the approximate probability of it happening, if we were to assume a lognormal model of the market.

Without loss of generality, we will use 90 days trailing data to calculate the mean and volatility of stock returns. As of last Thursday (the day of the fall), the daily mean returns for FB was 0.204%, or an annualised return of 51.5% (as you can see, very impressive!). The daily volatility in the stock (using a 90-day lookback period again) was 1.98%, or an annualised volatility of 31.4% . While it is a tad on the higher side, it is okay considering the annual return of 51.5%.

Now, traditional quantitative finance models have all used a lognormal distribution to represent stock prices, which implies that the distribution of stock price returns is normal. Under such an assumption, the likelihood of a 18.9% drop in the value of Facebook (which is what we saw on Thursday) is very small indeed.

In fact, to be precise, when the stock is returning 0.204% per day with a vol of 1.98% per day, the an 18.9% drop is a 9.7 sigma event. In other words, if the distribution of returns were to be normal, Thursday’s drop is 9 sigmas away from normal. Remember that most quality control systems (admittedly in industrial settings, where faults are indeed governed by a nearly normal distribution) are set for a six sigma limit.

Another way to look at Thursday’s 9.7 sigma event is that again under the normal distribution, the likelihood of seeing this kind of a fall in a day is $math ~10^{-21}$. Or one in a billion trillion. In terms of the number of trading days required for such a fall to arrive at random, it is of the order of a billion billion years, which is an order of magnitude higher than the age of the universe!

In fact, when the 1987 stock market crash (black monday) happened, this was the defence the quants gave for losing their banks’ money – that it was an incredibly improbable event. Now, my reading of the papers nowadays is sketchy, and I mostly consume news via twitter, but I haven’t heard a single such defence from quants who lost money in the Facebook crash. In fact, I haven’t come across too many stories of people who lost money in the crash.

Maybe it’s the power of diversification, and maybe indexing, because of which Facebook is now only a small portion of people’s portfolios. A 20% drop in a stock that is even 10% of your portfolio erodes your wealth by 2%, which is tolerable. What possibly caused traders to jump out of windows on Black Monday was that it was a secular drop in the US market then.

Or maybe it’s that the lessons learnt from Black Monday have been internalised, and included in models 30 years hence (remember that concepts such as volatility smiles and skews, and stochastic volatility, were introduced in the wake of the 1987 crash).

That a 20% drop in one of the five biggest stocks in the United States didn’t make for “human stories” or stories about “one in a billion billion event” is itself a story! Or maybe my reading of the papers is heavily biased!

PostScript

Even after the spectacular drop, the Facebook stock at the time of this update is trading at 168.25, a level last seen exactly 3 months ago – on 26th April, following the last quarter results of Facebook. That barely 3 months’ worth of earnings have been wiped out by such a massive crash suggests that the only people to have lost from the crash are traders who wrote out of the money puts.


text:
Definition 37.20.1. Let $f : X \to Y$ be a morphism of schemes. Assume that all the fibres $X_ y$ are locally Noetherian schemes.

1. Let $x \in X$, and $y = f(x)$. We say that $f$ is Cohen-Macaulay at $x$ if $f$ is flat at $x$, and the local ring of the scheme $X_ y$ at $x$ is Cohen-Macaulay.

2. We say $f$ is a Cohen-Macaulay morphism if $f$ is Cohen-Macaulay at every point of $X$.

There are also:

• 3 comment(s) on Section 37.20: Cohen-Macaulay morphisms

In your comment you can use Markdown and LaTeX style mathematics (enclose it like $\pi$). A preview option is available if you wish to see how it works out (just click on the eye in the toolbar).


text:
# Prove every automorphism can be realized as conjugation

Let $N$ be a group, and $\alpha : N \to N$ be an automorphism. Prove that $\alpha$ may be realized as a conjugation. i.e., there exists a group $G$ containing $N$ as a normal subgroup with $\alpha(n) = gng^{-1}$ for some $g \in G$.

I'm guessing the way to do this is to construct $G$ as a semi-direct product of $N$ with some cleverly chosen group $H$...but I'm stuck at picking the right $G$ or $H$. This problem comes from Aluffi exercise IV.5.7

-

You're very close. Remember that $\alpha$ is an element of the group $\operatorname{Aut}(N)$, so as ever there is a homomorphism $\theta\colon \mathbf{Z} \to \operatorname{Aut}(N)$ determined by $\theta(1) = \alpha$. This more or less does the job, although you could certainly say something extra in the case where $\theta$ has a non-trivial kernel.

-
Great! Then the conjugation happens in $N \rtimes_{\theta} \mathbb{Z}$, and with some careful steps to not mix up the group operations in $\mathbb{Z}$ and $N$, the conjugation works out. –  JeremyKun Oct 15 '11 at 20:47
@Bean: Is your problem to realize each automorphism as conjugation, with possibly different automorphisms being realized as conjugations in different groups, or to find a single group in which every automorphism is realized as conjugation in that group? –  Arturo Magidin Oct 15 '11 at 21:08
The automorphism $\alpha$ is fixed from the beginning. Dylan's hint led me to the solution. –  JeremyKun Oct 15 '11 at 21:22
@Bean: Ah, I misunderstood the problem, then. The solution I give below gives you a group in which you can realize all automorphisms in the same group; Dylan's solution is far simpler if all you care about is a single automorphism. –  Arturo Magidin Oct 15 '11 at 21:43

The simplest thing is to remember that a semidirect product $N\rtimes K$ of groups $N$ and $K$ is equivalent to a group homomorphism $\phi\colon K\to\mathrm{Aut}(N)$: given a semidirect product $N\rtimes K$, we obtain $\phi$ by letting $\phi(k)$ be the automorphism induced on $N$ by conjugation by $k$ in $N\rtimes K$. Conversely, given a homomorphism $\phi\colon K\to\mathrm{Aut}(N)$, we construct the semidirect product $N\rtimes_{\phi}K$ as the group whose underlying set is the set $N\times K$ of all ordered pairs $(n,k)$ with $n\in N$, $k\in K$, and with group operation given by $$(n,k)\cdot (m,\ell) = (n\phi(k)(m), k\ell).$$ In this group, we have that $$(e,k)(n,e)(e,k)^{-1} = (e,k)(n,e)(e,k^{-1}) = (e\phi(k)(n)e,kk^{-1}) = (\phi(k)(n),e).$$ That is, conjugation by $(e,k)$ corresponds exactly to the application of $\phi(k)$ to $N$. We then identify $N$ with the subgroup $\{(n,e)\mid n\in N\}$, and $K$ with the subgroup $\{(e,k)\mid k\in K\}$.

So to get a semidirect product you want to find some group $K$ and a group homomorphism $\phi\colon K\to\mathrm{Aut}(N)$. Then conjugation by $k$ in $N\rtimes K$ will correspond to the automorphism $\phi(k)$. Since we want every automorphism to be represented, we want $\phi$ to be onto. And that's really all we need.

So... we just need to find some group $K$ that has an onto homomorphism to $\mathrm{Aut}(N)$. What's the simplest one and simplest $\phi$ we can find?

-


text:
Milman's reverse Brunn–Minkowski inequality

In mathematics, particularly, in asymptotic convex geometry, Milman's reverse Brunn–Minkowski inequality is a result due to Vitali Milman[1] that provides a reverse inequality to the famous Brunn–Minkowski inequality for convex bodies in n-dimensional Euclidean space Rn. Namely, it bounds the volume of the Minkowski sum of two bodies from above in terms of the volumes of the bodies.

Introduction

Let K and L be convex bodies in Rn. The Brunn–Minkowski inequality states that

$\mathrm{vol}(K+L)^{1/n} \geq \mathrm{vol}(K)^{1/n} + \mathrm{vol}(L)^{1/n}~,$

where vol denotes n-dimensional Lebesgue measure and the + on the left-hand side denotes Minkowski addition.

In general, no reverse bound is possible, since one can find convex bodies K and L of unit volume so that the volume of their Minkowski sum is arbitrarily large. Milman's theorem states that one can replace one of the bodies by its image under a properly chosen volume-preserving linear map so that the left-hand side of the Brunn–Minkowski inequality is bounded by a constant multiple of the right-hand side.

The result is one of the main structural theorems in the local theory of Banach spaces.[2]

Statement of the inequality

There is a constant C, independent of n, such that for any two centrally symmetric convex bodies K and L in Rn, there are volume-preserving linear maps φ and ψ from Rn to itself such that for any real numbers st > 0

$\mathrm{vol} ( s \, \varphi K + t \, \psi L )^{1/n} \leq C \left( s\, \mathrm{vol} ( \varphi K )^{1/n} + t\, \mathrm{vol} ( \psi L )^{1/n} \right)~.$

One of the maps may be chosen to be the identity.[3]

References

• Milman, Vitali D. (1986). "Inégalité de Brunn-Minkowski inverse et applications à la théorie locale des espaces normés. [An inverse form of the Brunn-Minkowski inequality, with applications to the local theory of normed spaces]". C. R. Acad. Sci. Paris Sér. I Math. 302 (1): 25–28. MR 0827101.
• Pisier, Gilles (1989). The volume of convex bodies and Banach space geometry. Cambridge Tracts in Mathematics 94. Cambridge: Cambridge University Press. ISBN 0-521-36465-5. MR 1036275.


text:
### Efficient Lattice-Based Inner-Product Functional Encryption

Jose Maria Bermudo Mera, Angshuman Karmakar, Tilen Marc, and Azam Soleimanian

##### Abstract

In the recent years, many research lines on Functional Encryption (FE) have been suggested and studied regarding the functionality, security, or efficiency. Nevertheless, an open problem on a basic functionality, the single-input inner-product (IPFE), remains: can IPFE be instantiated based on the Ring Learning With Errors (RLWE) assumption? The RLWE assumption provides quantum-resistance security while in comparison with LWE assumption gives significant performance and compactness gains. In this paper we present the first RLWE-based IPFE scheme. We carefully choose strategies in the security proofs to optimize the size of parameters. More precisely, we develop two new results on ideal lattices. The first result is a variant of Ring-LWE, that we call multi-hint extended Ring-LWE, where some hints on the secret and the noise are given. We present a reduction from RLWE problem to this variant. The second tool is a special form of Leftover Hash Lemma (LHL) over rings, known as Ring-LHL. To demonstrate the efficiency of our scheme we provide an optimized implementation of RLWE-based IPFE scheme and show its performance on a practical use case. We further present new compilers that, combined with some existing ones, can transfer a single-input FE to its (identity-based, decentralized) multi-client variant with linear size of the ciphertext (w.r.t the number of clients).

Available format(s)
Category
Public-key cryptography
Publication info
Published by the IACR in PKC 2022
Keywords
Functional EncryptionInner-ProductLattice-Based CryptographyLearning with Errors over Ring
Contact author(s)
tilen marc @ xlab si
History
2021-12-24: revised
See all versions
Short URL
https://ia.cr/2021/046

CC BY

BibTeX

@misc{cryptoeprint:2021/046,
author = {Jose Maria Bermudo Mera and Angshuman Karmakar and Tilen Marc and Azam Soleimanian},
title = {Efficient Lattice-Based Inner-Product Functional Encryption},
howpublished = {Cryptology ePrint Archive, Paper 2021/046},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/046}},
url = {https://eprint.iacr.org/2021/046}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.


text:
# How to denote the space complexity in terms of output

Normally the space complexity of an Algorithm $A$ is denoted $\textrm{SPACE}(A)$, which means how much space is needed by the computation itself. I would however like to also describe how much storage an algorithm needs, i.e. if I have a Turing Machine with three tapes, one for the input, one for the computation, and one for the output, I would like to express the size of each one of them.

Is there a standard way of doing so? If so, is there a reference?

Currently I am using the symbol $\textrm{DATA}$. As an example consider function $list(n) = (1,\dots,n)$. The respective algorithm $List$ for computing the function $list$ is s.t. $\textrm{TIME}(List(n)) \in \mathcal{O}(n)$, since we need to write $n$ symbols, $\textrm{SPACE}(List(n)) = \mathcal{O}(1)$, since we only need to store the current symbol, and $\textrm{DATA}(List(n)) = \mathcal{O}(n)$, since the output is a vector of length $n$.

If your algorithm/TM is called $A$ and the input $x$, it is customary to denote the size of the output by using function and string notation, that is $|A(x)|$.


text:
zbMATH — the first resource for mathematics

Examples
 Geometry Search for the term Geometry in any field. Queries are case-independent. Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact. "Topological group" Phrases (multi-words) should be set in "straight quotation marks". au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted. Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff. "Quasi* map*" py: 1989 The resulting documents have publication year 1989. so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14. "Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic. dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles. py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses). la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
 a & b logic and a | b logic or !ab logic not abc* right wildcard "ab c" phrase (ab c) parentheses
Fields
 any anywhere an internal document identifier au author, editor ai internal author identifier ti title la language so source ab review, abstract py publication year rv reviewer cc MSC code ut uncontrolled term dt document type (j: journal article; b: book; a: book article)
Dynamic behaviors of the Ricker population model under a set of randomized perturbations. (English) Zbl 0952.92025
Summary: We studied the dynamics of the Ricker population model under perturbations by the discrete random variable $\varepsilon$ which follows distribution $P\{\varepsilon= a_i\}=p_i$, $i=1,\dots,n$, $0<a_i\ll 1$, $n\ge 1$. Under the perturbations, $n+1$ blurred orbits appeared in the bifurcation diagram. Each of the $n+1$ blurred orbits consisted of $n$ sub-orbits. The asymptotes of the $n$ sub-orbits in one of the $n+1$ blurred orbits were $N_t= a_i$ for $i=1,\dots,n$. For other $n$ blurred orbits, the asymptotes of the $n$ sub-orbits were $N_t=a_i \exp[r(1-a_i)]+a_j$, $j=1,2,\dots,n$, for $i=1, \dots, n$, respectively. The effects of variances of the random variable $\varepsilon$ on the bifurcation diagrams were examined. As the variance value increased, the bifurcation diagram became more blurred. Perturbation effects of the approximate continuous uniform random variable and random error were compared. The effects of the two perturbations on dynamics of the Ricker model were similar, but with differences. Under different perturbations, the attracting equilibrium points and two-cycle periods in the Ricker model were relatively stable. However, some dynamic properties, such as the periodic windows and the $n$-cycle periods $(n>4)$, could not be observed even when the variance of a perturbation variable was very small. The process of reversal of the period-doubling, an important feature of the Ricker and other population models observed under constant perturbations, was relatively unstable under random perturbations.

MSC:
 92D25 Population dynamics (general) 37N25 Dynamical systems in biology 37H99 Random dynamical systems
Full Text:
References:
 [1] Berryman, A. A.; Millstein, J. A.: Are ecological systems chaotic -- and if not, why not?. Trends in ecol. Evol. 4, 26 (1989) [2] Turchin, P.; Taylor, A. D.: Complex dynamics in ecological time series. Ecology 73, 289 (1992) [3] Ellner, S.; Turchin, P.: Chaos in a noisy world: new methods and evidence for time series analysis. Am. natural. 145, 343 (1995) [4] Higgins, K.; Hastings, A.; Sarvela, J. N.; Botsford, L. W.: Stochastic dynamics and deterministic skeletons: population behavior of dungeness crab. Science 276, 1431 (1997) · Zbl 1225.60113 [5] Pimm, S. L.: The complexity and stability of ecosystems. Nature 307, 321 (1984) [6] Scheuring, I.; Janosi, I. M.: When two and two make four: a structured population without chaos. J. theoret. Biol. 178, 89 (1996) [7] Stone, L.: Coloured noise or low-dimensional chaos?. Proc. roy. Soc. London B 250, 77 (1992) [8] Sun, P.; Yang, X. B.: Two properties of a gene-for-gene coevolution system under human perturbations. Phytopathology 89, 811 (1999) [9] Mccallum, H. I.: Effects of immigration on population dynamics. J. theoret. Biol. 154, 277 (1992) [10] Stone, L.: Period-doubling reversals and chaos in simple ecological models. Nature 36, 617 (1993) [11] Rohani, P.; Miramontes, O.; Hassell, M. P.: Quasiperiodicity and chaos in population models. Proc. roy. Soc. London B 258, 17 (1994) [12] Rohani, P.; Miramontes, O.: Immigration and the persistence of chaos in population models. J. theoret. Biol. 175, 203 (1995) [13] Doebeli, M.: Dispersal and dynamics. Theoret. populat. Biol. 47, 82 (1995) · Zbl 0814.92015 [14] Sun, P.; Yang, X. B.: Deterministic property changes in population models under random error perturbations. Ecological modelling 119, 239 (1999) [15] Laha, R. G.; Rohatgi, V. K.: Probability theory. (1979) · Zbl 0409.60001 [16] Serfling, R. J.: Approximation theorems of mathematical statistics. (1980) · Zbl 0538.62002 [17] Drake, V. A.; Gatehouse, A. G.: Insect migration: tracking resources through space and time. (1995) [18] Wiktelius, S.: Long-range migration of aphids into Sweden. Int. J. Biometerol. 28, 200 (1984) [19] P. Sun, The studies of aphid population dynamics and its control in the fields of winter wheat in Hebei Province, PhD Thesis, Peking University, 1991 [20] Yang, X. B.; Zeng, S. M.: Detecting patterns of wheat stripe rust pandemics in time and space. Phytopathology 82, 571 (1992) [21] Zeng, S. M.: Pancrin a prototype model of the pandemic cultivar-race interaction of yellow rust of wheat in China. Plant pathol. 40, 287 (1991) [22] Beaumont, G. P.: Probability and random variables. (1986) · Zbl 0588.60002 [23] Cruthfield, J. P.; Farmer, J. D.; Huberman, B. A.: Fluctuations and simple chaotic dynamics. Phys. rep. 92, 45 (1982) [24] Schaffer, W. M.; Ellner, S.; Kot, M.: Effects of noise on some dynamical models in ecology. J. math. Biol. 24, 479 (1986) · Zbl 0626.92021 [25] Ripa, J.; Lundberg, P.: Noise colour and the risk of population extinctions. Proc. roy. Soc. London B 263, 1751 (1996) [26] Rossler, J.; Kiwi, M.; Hess, B.; Markus, M.: Modulated non-linear and a novel mechanism to induce chaos. Phys. rev. A 39, 5954 (1989) [27] Sun, P.; Yang, X. B.: The stability of gene-for-gene coevolution model under constant perturbations. Phytopathology 88, 592 (1998) [28] Barnsley, M.: Fractals everywhere. (1993) · Zbl 0784.58002 [29] May, R. M.: Detecting density dependence in imaginary world. Nature 338, 16 (1989) [30] Jin, Z.: A brief introduction to chaos. Math. prac. Theor. 12, 81 (1991) [31] Levin, S. A.; Grenfell, B.; Hastings, A.; Perelson, A. S.: Mathematical and computational challenges in population biology and ecosystems science. Science 275, 334 (1997) · Zbl 1225.92058